419 PurleyFunctional.tv Newsletter

00 String difference.md

String difference

You are given two strings, a and b. We consider each letter to be unique, meaning duplicates are significant. Write a function that returns the count of letters in b which do not occur in a.

Examples

(strdiff "abc" "") ;=> {} ;; no characters in b don't occur in a
(strdiff "abc" "abc") ;=> {} ;; ditto
(strdiff "" "abc") ;=> {\a 1 \b 1 \c 1}
(strdiff "axx" "abcc") ;=> {\b 1 \c 2}
(strdiff "xxxx" "xxxxxx") ;=> {\x 2} ;; two x's in b that don't occur in a

Thanks to this site for the challenge idea where it is considered Hard in Python. The problem has been modified from the original.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

Thanks.

(defn update-freq-map [m k v]
  (if (get m k)
    (update m k #(- % v))
    m))

(defn dissoc-less-one [m]
  (let [less-one-key (->> m
                          (filter (fn [[_ v]] (< v 1)))
                          (map first))]
    (reduce
     (fn [m k] (dissoc m k))
     m
     less-one-key)))

(defn strdiff [a b]
  (let [freq-a (frequencies a)
        freq-b (frequencies b)]
    (->> (reduce-kv
          update-freq-map
          freq-b
          freq-a)
         dissoc-less-one)))

(defn strdiff [a b]
  (loop [freq-b (frequencies b)
         acc {}]
    (cond
      (or (= a b) (empty? freq-b)) acc
      (empty? a) freq-b
      :else
      (let [[k vb] (first freq-b)
            va ((frequencies a) k 0)
            diff (- vb va)]
        (if (pos-int? diff)
          (recur (rest freq-b) (assoc acc k diff))
          (recur (rest freq-b) acc))))))