DSA Find All Anagrams in a String

The problem

Find All Anagrams in a String lists every start index where a stretch of the text holds exactly the pattern's letters. An anagram uses the same letters with the same counts, in any order.

The text and the pattern use lowercase letters only. Each matching stretch has the pattern's length. Overlapping matches all count.

cases = [
    ("cbaebabacd", "abc", [0, 6]),
    ("abab", "ab", [0, 1, 2]),
    ("aaa", "aa", [0, 1]),
    ("xyz", "ab", []),
]
for text, pattern, expected in cases:
    print("text", text, "pattern", pattern, "starts:", expected)

Read one row at a time. In the first row, the stretches at index 0 and index 6 each hold one a, one b and one c. The last row holds no matching stretch at all.

Intuition: cut each window out and sort it

The first idea cuts out each stretch of the pattern's length. It then sorts the stretch and sorts the pattern. Equal sorted forms mean the stretch is an anagram.

The idea always works. Its cost is the trap. The same letters get sorted again at every position, even though one slide changes only two letters.

text = "cbaebabacd"
pattern = "abc"
size = len(pattern)
target = sorted(pattern)
matches = []
sorts = 0
for start in range(len(text) - size + 1):
    piece = text[start:start + size]
    sorts += 1
    if sorted(piece) == target:
        matches.append(start)
print("windows sorted:", sorts)
print("matches:", matches)

Eight windows meant eight sorts for one text. Almost all of that sorting repeats work from the window before. Only one letter leaves and one letter enters per step.

Brute force: recount every window from scratch

The brute force keeps the counting idea and drops the sorting. It builds a fresh count table for every window. A counter records how many letters get counted.

A count table here has 26 slots, one per lowercase letter. Slot zero counts the letter a. Two equal tables mean the window is an anagram.

def find_brute(text, pattern):
    size = len(pattern)
    need = [0] * 26
    for ch in pattern:
        need[ord(ch) - ord("a")] += 1
    starts = []
    counted = 0
    for start in range(len(text) - size + 1):
        window = [0] * 26
        for ch in text[start:start + size]:
            window[ord(ch) - ord("a")] += 1
            counted += 1
        if window == need:
            starts.append(start)
    return starts, counted

starts, counted = find_brute("cbaebabacd", "abc")
print("starts:", starts)
print("letters counted:", counted)
starts, counted = find_brute("abab", "ab")
print("starts:", starts)
print("letters counted:", counted)

The first text counted 24 letters to check 8 windows. Each window paid full price for its three letters. A longer pattern makes that repeat cost larger, not smaller.

The optimal solution: slide one count table

One count table slides with the window, losing the leaving letter and gaining the entering letter, so each position costs two updates and one table comparison. That one sentence is the whole method.

The window length never changes. An anagram has the pattern's length, so a fixed size is correct. Comparing two 26-slot tables costs at most 26 steps, so each slide stays cheap.

def find_anagrams(text, pattern):
    size = len(pattern)
    if size > len(text):
        return []
    need = [0] * 26
    for ch in pattern:
        need[ord(ch) - ord("a")] += 1
    window = [0] * 26
    starts = []
    for i, ch in enumerate(text):
        window[ord(ch) - ord("a")] += 1
        if i >= size:
            window[ord(text[i - size]) - ord("a")] -= 1
        if i >= size - 1 and window == need:
            starts.append(i - size + 1)
    return starts

cases = [
    ("cbaebabacd", "abc", [0, 6]),
    ("abab", "ab", [0, 1, 2]),
    ("aaa", "aa", [0, 1]),
    ("xyz", "ab", []),
]
for text, pattern, expected in cases:
    result = find_anagrams(text, pattern)
    print("text", text, "pattern", pattern, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The overlapping rows pass because the table updates instead of restarting. A match never stops the slide.

Walkthrough: pattern ab in abab

The walk visits one letter at a time. The state is the window and its counts for a and b. Each step adds one letter, drops the letter that falls out, and tests the table.

text = "abab"
pattern = "ab"
size = len(pattern)
need = [0] * 26
for ch in pattern:
    need[ord(ch) - ord("a")] += 1
window = [0] * 26
for i, ch in enumerate(text):
    window[ord(ch) - ord("a")] += 1
    if i >= size:
        window[ord(text[i - size]) - ord("a")] -= 1
    if i >= size - 1:
        piece = text[i - size + 1:i + 1]
        print("window", piece, "- a:", window[0], "b:", window[1], "- match:", window == need, "- start:", i - size + 1)

Every full window matches here. The counts return to one a and one b after each slide. The start index moves by one each time, and each start joins the answer.

Complexity

The brute force counts the pattern length for each of the text's windows, so its time is O(n times m) for a text of length n and a pattern of length m. The sliding table does two updates and one fixed-size comparison per letter, so its time is O(n).

Both methods store two 26-slot tables and the answer list. The extra space beyond the answer is O(1), because 26 slots never grow with the input.

for n, m in [(10, 3), (20, 3), (40, 3)]:
    windows = n - m + 1
    print("text", n, "pattern", m, "- brute letters counted:", windows * m, " slide updates:", 2 * n)

Counts beat clocks here. At 40 letters the recount pays 114 letter counts against 80 slide updates. The gap widens fast when the pattern grows, because the recount pays per window and the slide does not.

Edge cases and pitfalls

A pattern longer than the text has no window at all. The answer is an empty list, not an error. The function tests that case before building any window.

Repeated letters are the classic counting trap. The pattern aa needs two copies of a in the window. A set of letters would wrongly accept a single a, because a set forgets counts.

def find_anagrams(text, pattern):
    size = len(pattern)
    if size > len(text):
        return []
    need = [0] * 26
    for ch in pattern:
        need[ord(ch) - ord("a")] += 1
    window = [0] * 26
    starts = []
    for i, ch in enumerate(text):
        window[ord(ch) - ord("a")] += 1
        if i >= size:
            window[ord(text[i - size]) - ord("a")] -= 1
        if i >= size - 1 and window == need:
            starts.append(i - size + 1)
    return starts

print("overlapping matches:", find_anagrams("aaa", "aa"))
print("pattern longer than text:", find_anagrams("ab", "abc"))
print("no match:", find_anagrams("xyz", "ab"))
print("empty text:", find_anagrams("", "a"))
print("whole text matches:", find_anagrams("bca", "abc"))

The overlap row works because the shared letter stays inside the window across the slide. Its count stays in the table the whole time. A match is only tested once the window is full, so the short opening window never joins the answer by mistake.