VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.7 of 16 in this moduleFree

Valid Anagram

Are two strings rearrangements of each other? From trying permutations to sorting, then a 26-slot count array in O(n) time and O(1) space, and what changes for Unicode, streams and grouping many words by signature.

about 10 min 7 Python examples 2 quick checks

Problem. Given strings s and t, return True if t is an anagram of s: the same letters with the same counts, in any order.

text
s = "listen", t = "silent"   →   True
s = "rat",    t = "car"      →   False

ML context. "Same multiset, any order" is the bag-of-words idea: two documents with the same token counts look identical to a bag-of-words model. Count vectors (histograms) are also how you compare label distributions between a training and a serving set, and how you deduplicate records whose fields arrive in a different order.

The lesson: the right representation makes the comparison trivial. Order is noise here; counts are the signal.


1. Step 1: Clarify

Question Answer Why it matters
Which characters? Lowercase a–z (for now) A fixed alphabet allows a 26-slot array
Case and spaces significant? Yes, compare as given Normalising is a separate choice
Lengths? Up to 5 × 10⁴ Rules out anything factorial or quadratic
Different lengths? Then False immediately A free O(1) early exit

2. Step 2: Brute force

The most literal reading: "is t one of the rearrangements of s?" Generate every permutation and compare.

python
from itertools import permutations


def is_anagram_perm(s, t):
    if len(s) != len(t):
        return False
    return any("".join(p) == t for p in permutations(s))    # n! permutations


assert is_anagram_perm("abc", "cab")
assert not is_anagram_perm("rat", "car")
print("permutation brute force works, but only for tiny strings: O(n! · n)")

O(n! · n) time. At n = 12 that's already about 5.7 × 10⁹ operations; at n = 5 × 10⁴ it's unthinkable.

A slightly better brute force: for each character of s, find and remove one matching character from t.

python
def is_anagram_remove(s, t):
    if len(s) != len(t):
        return False
    pool = list(t)
    for ch in s:
        if ch not in pool:        # O(n) search
            return False
        pool.remove(ch)           # O(n) shift
    return True


assert is_anagram_remove("listen", "silent")
assert not is_anagram_remove("aab", "abb")
print("match-and-remove works: O(n²) time, O(n) space")

O(n²) time: at n = 5 × 10⁴ about 2.5 × 10⁹ steps. Still too slow, so optimise.


3. Step 3: Optimise: find a canonical form

First principles. Two strings are anagrams exactly when they have the same canonical form: one representation that forgets order but keeps everything else. There are two natural ones.

Optimisation A: sort both strings

Sorting puts letters in a fixed order, so anagrams become equal strings.

python
def is_anagram_sort(s, t):
    return len(s) == len(t) and sorted(s) == sorted(t)


assert is_anagram_sort("listen", "silent")
assert not is_anagram_sort("rat", "car")
print("sort version: O(n log n) time, O(n) space for the sorted copies")

O(n log n) time, O(n) space. Simple, and it works for any characters. But sorting does more work than needed: we don't care about the order of letters at all, only how many of each.

Optimisation B: count with a fixed-size array

With the alphabet fixed to a–z, a list of 26 counters is the canonical form. Add 1 for each letter of s, subtract 1 for each letter of t; anagrams leave every counter at zero.

count arrays for "listen" and "silent" over the letters e, i, l, n, s, t; every count is 1 in both, so the difference array is all zeros and the strings are anagrams.
Diagram— count arrays for "listen" and "silent" over the letters e, i, l, n, s, t; every count is 1 in both, so the difference array is all zeros and the strings are anagrams.
python
import random
import string


def is_anagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26                          # fixed size: O(1) space
    for a, b in zip(s, t):
        counts[ord(a) - ord("a")] += 1
        counts[ord(b) - ord("a")] -= 1
    return all(c == 0 for c in counts)


def reference(s, t):
    return sorted(s) == sorted(t)


assert is_anagram("listen", "silent")
assert not is_anagram("rat", "car")
assert is_anagram("", "")
rng = random.Random(16)
for _ in range(1000):
    s = "".join(rng.choice("abcde") for _ in range(rng.randint(0, 10)))
    t = list(s)
    rng.shuffle(t)
    if rng.random() < 0.5 and t:
        t[rng.randrange(len(t))] = rng.choice(string.ascii_lowercase)   # maybe break it
    t = "".join(t)
    assert is_anagram(s, t) == reference(s, t)
print("26-slot count array: O(n) time, O(1) space, matches sorting on 1,000 cases")
  • Time: O(n): one pass, plus 26 checks.
  • Space: O(1): 26 counters, however long the strings are. ("O(alphabet)" is the honest way to say it.)
  • Why one array, not two: incrementing for s and decrementing for t compares the two histograms as you build them, so a single final check suffices.

Quick check

Why is the 26-slot counting array O(1) space even for strings of length 10⁶?

  1. Python compresses lists
  2. Its size depends only on the alphabet (26), not on the input length; it's really O(alphabet), which is constant once the alphabet is fixed
  3. The strings are deleted as you go
  4. It isn't; it's O(n)
Show the answer

B. Its size depends only on the alphabet (26), not on the input length; it's really O(alphabet), which is constant once the alphabet is fixed — Space is measured against the input size n; a fixed 26-slot array doesn't grow with n.


4. When the constraints change

a decision map: sort when simplicity matters or characters are arbitrary, a 26-slot array for lowercase letters, a Counter (hash map) for Unicode, and sorted-word or count-tuple signatures for grouping many words.
Diagram— a decision map: sort when simplicity matters or characters are arbitrary, a 26-slot array for lowercase letters, a Counter (hash map) for Unicode, and sorted-word or count-tuple signatures for grouping many words.

Change A: the strings contain any Unicode character

A 26-slot array no longer fits (there are over a million code points). Switch the counter to a hash map: same idea, O(n) time, O(distinct characters) space.

python
from collections import Counter


def is_anagram_unicode(s, t):
    return len(s) == len(t) and Counter(s) == Counter(t)


assert is_anagram_unicode("débruit", "tiburdé")
assert is_anagram_unicode("नमस्ते", "स्तेनम")
assert not is_anagram_unicode("ab", "aa")
print("Counter version handles any characters: O(n) time, O(distinct) space")

A subtle trap worth naming in an interview: "é" can be one code point or "e" plus a combining accent. If the input may mix both, normalise first (unicodedata.normalize("NFC", s)), or anagrams can look different.

Change B: group many words into anagram families

Given a list of words, group the anagrams together. Comparing every pair is O(m² · k) for m words of length k. Instead, compute each word's signature (its canonical form) once and use it as a dictionary key.

python
from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        counts = [0] * 26
        for ch in w:
            counts[ord(ch) - ord("a")] += 1
        groups[tuple(counts)].append(w)        # the count tuple is hashable: O(k) per word
    return list(groups.values())


result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(sorted(g) for g in result) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
print("signature grouping: O(m · k) time instead of O(m² · k)")

The key choice is a mini trade-off: "".join(sorted(w)) costs O(k log k) per word and is short; the count tuple costs O(k + 26) and wins for long words. That's the same sort-versus-count decision as the main problem.

Change C: the second string arrives as a stream

Build the counts for s first, then decrement as each character of t arrives. Stop as soon as a count goes negative: t has used a letter more often than s has it. O(1) memory per character, early exit for free.

python
def is_anagram_stream(s, t_stream):
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    remaining = len(s)
    for ch in t_stream:
        i = ord(ch) - ord("a")
        counts[i] -= 1
        if counts[i] < 0:
            return False                     # t has too many of this letter: stop now
        remaining -= 1
    return remaining == 0


assert is_anagram_stream("listen", iter("silent"))
assert not is_anagram_stream("listen", iter("silents"))
assert not is_anagram_stream("listen", iter("sile"))
print("streaming check works, with an early exit")

The full table

If the constraint becomes… Best approach Time Space
Any characters, simplest code Sort both O(n log n) O(n)
Lowercase a–z 26-slot count array O(n) O(1)
Unicode text Counter (hash map), normalise first O(n) O(distinct)
Group m words of length k Signature → dictionary O(m · k) O(m · k)
One string arrives as a stream Count s, decrement on arrival, early exit O(n) O(1)
Compare two large documents as bags of words Token Counter per document O(n) O(vocabulary)

Quick check

You need to group 10⁵ words into anagram families. Which approach scales?

  1. Compute each word's canonical signature (sorted letters or a count tuple) once and use it as a dictionary key: one pass over the words
  2. Compare every pair of words with an anagram check
  3. Sort the list of words alphabetically
  4. Generate every permutation of each word
Show the answer

A. Compute each word's canonical signature (sorted letters or a count tuple) once and use it as a dictionary key: one pass over the words — Pairwise checks are O(m²); a signature reduces grouping to one hash lookup per word.


5. Saying it out loud

"Trying permutations is factorial and match-and-remove is O(n²). Anagrams are exactly the strings with the same canonical form, so I can sort both, O(n log n), or, since the alphabet is a–z, keep 26 counters: add for s, subtract for t, and check they're all zero. That's O(n) time and O(1) space. For Unicode I'd use a Counter; to group many words I'd use the count tuple as a dictionary key."


Check yourself

  1. What is a "canonical form", and what are the two canonical forms used here?
  2. Why is the 26-slot array O(1) space?
  3. Why does incrementing for s and decrementing for t need only one final check?
  4. What changes for Unicode input, and what normalisation trap should you mention?
  5. How do you group anagrams without comparing every pair?
  6. How does the streaming version exit early?
Answers
  1. A representation that is equal for exactly the strings you want to treat as equal; here, the sorted string and the letter-count vector.
  2. Its size depends on the alphabet (26), not on n.
  3. The array holds count(s) − count(t) for each letter, so the strings match exactly when every entry is zero.
  4. Replace the array with a hash map; normalise (e.g. NFC) because the same visible character can have different code point sequences.
  5. Use each word's signature (sorted letters or count tuple) as a dictionary key: one pass, O(m · k).
  6. After counting s, decrement for each arriving character and return False as soon as any count goes negative.