You are given two strings s and t that consist only of lower-case letters. String t was created by adding one letter chosen at random to string s, then shuffling the resulting string. Find the letter that was added to t. For instance, the difference between the two strings “abcdef” and “bfxdeac” is the character “x”.

I could sort each string and then go character by character until they don't match, but that's O(n * log(n)). Making a "counter" for each string is O(n) and comparing them is constant time, so hash tables is definitely the right way to go about this.

At first I was super excited to try this in scheme because hash tables strike me as super non-functional! It turns out there are actually pretty functional ways to do this, so the fun part ended up being playing with different ways to control state.

First the easy part:

; this one defines a variable:
(define lowercase-letters (string->list "abcdefghijklmnopqrstuvwxyz"))
; this one defines a function:
(define (increment x) (+ x 1))

I couldn't find a good function for making a counter hash table, so I'll have to define it myself. There's a number of ways I could do this. First, the "imperative", "mutable" way:

(define (count-chars-mut string)
  ; First make a hash table called counts:
  (define counts (make-hash)) 
  ; now for each character in the string, update the hash table:
  (for-each (lambda (char) (hash-update! counts char increment 0))
    (string->list string))
  ; return the hash table:
  counts)

Scheme documentation explains that for-each is like map except that it's used for its side effects, so it doesn't return anything. The exclamation mark in hash-update! is a reminder that this function changes the state of something. The 0 argument to hash-update! means that if it tries to look up a key and there's no value it, it sets it to 0. This is pretty good, because even though there's multiple lines that run in order changing state as they go, it's wrapped up well inside a single function.

Another way to think of this is to solve it recursively (classic!). The counts for a string are the counts for the tail of the string (everything but the first character) with the count for the first character incremented (and the counts for an empty string are an empty hash table):

(define (count-chars-rec string)
  (if (string=? string "")
      (hash)  ; if the string is empty make an empty hash table
      (let ((head (string-ref string 0))
            (tail (substring string 1)))        
        ; otherwise, make a hash from the rest of the list and then increment it for the current character
        (hash-update (count-chars-rec tail) head increment))))

The fascinating thing here is that this uses "hash" instead of "make-hash" and "hash-update" instead of "hash-update!", using immutable hash tables! Every time hash-update is called it returns an entirely new hash table, representing the old hash table with the change applied.

Personally I think this is a little more straightforward if we define an inner function that takes a list of characters and uses "car" for head and "cdr" for tail:

(define (count-chars-list string)
  (define (inner chars)
    (if (empty? chars)
        (hash)
        ; "car" means the head of a list, "cdr" means the tail
        (hash-update (inner (cdr chars)) (car chars) increment 0)))
  (inner (string->list string)))

Finally, we can make this tail recursive:

(define (count-chars-iter string)
  (define (inner chars result)
    (if (empty? chars)
        result
        (inner (cdr chars) (hash-update result (car chars) increment 0))))
  (inner (string->list string) (hash)))

This time we call inner with a full list of characters and an empty hash table, and every time it calls itself one letter has been "moved" from "chars" into "result".

The last way I thought of to do this is using a common functional pattern, the "fold" (you've probably seen this, a looong time ago). We recognize that what we're doing here is taking a list, and somehow accumulating the values into a single result one at a time. We can do a fold if we know a starting value, and a function to incorporate each new value in the list into it. For example, I can write "sum" recursively like this:

(define (sum-rec list)
  (if (empty? list)
      0
      (+ (car list) (sum-rec (cdr list)))))

Or I can realize that I'm starting with zero, and using addition to combine the values in the list with it:

(define (sum list)
  (foldl + 0 list))

... and ...

(define (product list)  (foldl * 1 list))
(define (maximum list)  (foldl max -inf.0 list))

Etc.

In this case, we're starting with an empty hash table, and for each value incorporating it using hash-update:

(define (count-chars string)
  (define (count-char char hash) (hash-update hash char increment 0))
  (foldl count-char (hash) (string->list string)))

(I could do this in one line using a lambda, but I think it's more readable if I name "count-char")

OK now that I have a function to build the counter I guess I'm ready to solve this problem!

(define (extra-letter short-string long-string)
  ; get counts for each string
  (let ((short-count (count-chars short-string))
        (long-count (count-chars long-string))
    ; take a list of characters to compare the counts of
    (define (compare-letters chars)
      (let ((key (car chars)))
        (if (= (hash-ref long-count key 0)
               (+ 1 (hash-ref short-count key 0)))
            ; if the counts don't match, return the current character
            key
            ; otherwise try the rest
            (compare-letters (cdr chars)))))
    (compare-letters lowercase-letters)))

Now (extra-letter "abcdef" "bfxdeac") evaluates to #\x!

If I had done this in python:

from collections import Counter

def extra_letter(short_string, long_string):
    diff = Counter(long_string) - Counter(short_string)
    return list(diff.keys())[0]