Counting characters

Big idea

Many string questions ignore order and only care about how many of each character there are. Count once into a 26-slot array (or a hash map for larger alphabets), and anagram, "can it be built from", and "first unique" problems become O(n).

The count array

def counts(s):
    c = [0] * 26
    for ch in s:
        c[ord(ch) - ord('a')] += 1
    return c

For "listen": e:1, i:1, l:1, n:1, s:1, t:1. "silent" gives exactly the same array — so they're anagrams. Comparing two 26-slot arrays is O(26) = O(1).

Array or map? Use a 26-slot array when the problem promises lowercase letters — it's faster and simpler. Use a hash map (collections.Counter, HashMap<Character, Integer>) for arbitrary Unicode, mixed case, or whole words.

One array, add and subtract

Instead of building two arrays, add for one string and subtract for the other; they're anagrams if everything ends at zero:

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    c = [0] * 26
    for a, b in zip(s, t):
        c[ord(a) - ord('a')] += 1
        c[ord(b) - ord('a')] -= 1
    return all(x == 0 for x in c)

Watch it

Check whether rat and tar are anagrams with one count array.

"Can it be built from?"

Ransom Note: can note be written with letters cut from magazine, each used once? Count the magazine, then spend:

def can_construct(note, magazine):
    c = [0] * 26
    for ch in magazine:
        c[ord(ch) - ord('a')] += 1
    for ch in note:
        i = ord(ch) - ord('a')
        c[i] -= 1
        if c[i] < 0:
            return False      # needed one more than we had
    return True

First unique character

Two passes: count everything, then return the first index whose count is 1. Counting first is what lets the second pass answer in O(1) per character.

def first_unique(s):
    c = [0] * 26
    for ch in s:
        c[ord(ch) - ord('a')] += 1
    for i, ch in enumerate(s):
        if c[ord(ch) - ord('a')] == 1:
            return i
    return -1

Grouping by a signature

To group anagrams, give each word a key that every anagram shares, and bucket by it in a hash map:

• the sorted word: "eat" → "aet" (O(k log k) per word), or
• the count array as a tuple: (1,0,0,0,1,…,1,…) (O(k) per word).

"eat", "tea", and "ate" all land in the same bucket. Picking the right key is a hashing skill you'll reuse.

Mapping characters to characters

Isomorphic strings and word pattern ask whether there's a one-to-one mapping: "egg" ↔ "add" works (e→a, g→d), "foo" ↔ "bar" doesn't (o can't map to both a and r). Keep two maps, one each way, and fail on any conflict — one map alone misses the case where two letters map to the same target.

Practice

• Valid Anagram
• Ransom Note
• First Unique Character in a String
• Group Anagrams
• Isomorphic Strings

Quick check