UPDATED based on comments. Thanks guys!
Today's problem is to find the first non-repeating character in a string. If there are no non-repeating characters then we should indicate that also.
Here's how I broke down the problem. First I decided to group the characters in the string by their identity and index them based on the character's position in the string. For the string "abbc" this would produce a map like this:
{0 [\a] 1 [\b \b] 3 [\c]}
From there, I sort based on the index and drop all the pairs whose second element has a count > 1 until I reach my answer.
;;first non-repeating character (def test-str "aabcbcdeef") (defn find-non-repeat [some-str] (let [x (first (drop-while (fn [x] (> (count (last x)) 1)) (sort (group-by (fn [c] (.indexOf some-str (str c))) some-str))))] (if (nil? x) "No non-repeating characters" (str (first (last x))))))gist
I believe your solution doesn't guarantee to find the first such non-repeating character, so it does not meet the constraints of the problem.
ReplyDeleteAll of my tests shows that it works. Do you have a test string where it doesn't work?
ReplyDeleteI just checked the type returned by group-by and it's an array-map which will keep things in the order that they're inserted. That's why this works.
ReplyDeleteTry it on aabbccddeeffgghhiijjkkllmnopqr. Don't have a repl handy, but I strongly doubt you'll get m.
ReplyDeleteI tried it and I got "m".
ReplyDeleteI see. Strings happen to hash alphabetically, so it works out in that case. Now I have a repl handy, and it doesn't work for (find-non-repeat "aabbccddeeffgghhiijjkkllomp") - you still get m
ReplyDeleteYou're right. Running that returns a hash-map instead of an array-map. I wonder if the determination for what kind of map is returned is based on the length of the string.
ReplyDeleteYou could try something like this
ReplyDelete(defn solution-one [string]
(let [f (first string)
s (second string)]
(if (not= f s)
f
(recur (rest (rest string))))))
must be find-"first"-no-repeat because it shows only the first character no repeated...
ReplyDeletein the example it shows only d..no shows the f :(
i think must exist a easy way to accomplish this
The post at Programming Praxis stated that the solution should only find the first one. The answer is considered incorrect if it finds ones after that.
ReplyDelete(defn ++ ([old new] (if old (update-in old [0] inc) new)))
ReplyDelete(defn char-counter [s]
(let [index-s (map vector (repeat 0) (range) s)
char-map (reduce #(update-in %1 [(last %2)] ++ %2) {} index-s)]
(sort (vals char-map))))
char-counter will return a sequence of vectors ordered by the number of times a character appears and the offset into the string where it first appears.
char-counter "aabbccddeeffgghhiijjkkllomp")
([0 24 \o] [0 25 \m] [0 26 \p] [1 0 \a] [1 2 \b] [1 4 \c] [1 6 \d] [1 8 \e] [1 10 \f] [1 12 \g] [1 14 \h] [1 16 \i] [1 18 \j] [1 20 \k] [1 22 \l])
Then to get the first one you filter and map it
(first (map last (filter #(= (first %) 0) (char-counter "aabbccddeeffgghhiijjkkllomp"))))
\o
This comment has been removed by the author.
ReplyDeleteThis seems like a simple solution.
ReplyDelete(defn first-unique-char [s]
(let [f-map (frequencies s)]
(first (filter #(= 1 (get f-map %)) s))))
This comment has been removed by the author.
ReplyDelete(first (first (filter (fn [[k v]] (== 1 v)) (frequencies "gaabccbdeefg"))))
ReplyDelete; returns \d