Amazon

Friday, August 19, 2011

Programming Praxis: First Non-Repeating Character

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

15 comments:

  1. 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.

    ReplyDelete
  2. All of my tests shows that it works. Do you have a test string where it doesn't work?

    ReplyDelete
  3. I 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.

    ReplyDelete
  4. Try it on aabbccddeeffgghhiijjkkllmnopqr. Don't have a repl handy, but I strongly doubt you'll get m.

    ReplyDelete
  5. I 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

    ReplyDelete
  6. You'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.

    ReplyDelete
  7. You could try something like this

    (defn solution-one [string]
    (let [f (first string)
    s (second string)]
    (if (not= f s)
    f
    (recur (rest (rest string))))))

    ReplyDelete
  8. must be find-"first"-no-repeat because it shows only the first character no repeated...

    in the example it shows only d..no shows the f :(

    i think must exist a easy way to accomplish this

    ReplyDelete
  9. 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
  10. (defn ++ ([old new] (if old (update-in old [0] inc) new)))

    (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

    ReplyDelete
  11. This comment has been removed by the author.

    ReplyDelete
  12. This seems like a simple solution.

    (defn first-unique-char [s]
    (let [f-map (frequencies s)]
    (first (filter #(= 1 (get f-map %)) s))))

    ReplyDelete
  13. This comment has been removed by the author.

    ReplyDelete
  14. (first (first (filter (fn [[k v]] (== 1 v)) (frequencies "gaabccbdeefg"))))


    ; returns \d

    ReplyDelete