boot.user> (defn squeeze [s c]
  (if-let [i (clojure.string/index-of s c)]
    (str (subs s 0 i) (subs s (inc i)))
    false))
#'boot.user/squeeze
boot.user> (defn scramble? [s1 s2]
  (loop [s1 s1 s2 (seq s2)]
    (if (empty? s2)
      true
      (if-let [s1-stroke (squeeze s1 (first s2))]
        (recur s1-stroke (rest s2))
false))))
#'boot.user/scramble?

boot.user> (def str2 (apply str (repeat 1000 (shuffle (range 1000)))))
#'boot.user/str2
boot.user> (def str1 (apply str (repeat 1000 (shuffle (range 1000)))))
#'boot.user/str1
boot.user> (count str2)
396000
boot.user> (count str1)
391000
boot.user> (time (scramble? str1 str2))
"Elapsed time: 45675.783784 msecs"
false

boot.user> (defn scramble?
  [str1 str2]
  (let [f2 (into (sorted-map) (frequencies str2))
        f1 (select-keys (into (sorted-map) (frequencies str1)) (keys f2))]
    (if (< (count f1) (count f2))
      false
      (every? true? (map <= (vals f2) (vals f1))))))
#'boot.user/scramble?

boot.user> (time (scramble? str1 str2))
"Elapsed time: 125.848442 msecs"
false