Find All Anagrams in a String – Solution & Complexity

Q: What is the time and space complexity of Find All Anagrams in a String?

The optimal Find All Anagrams in a String solution runs in `O(n)` time and `O(1)` space. Slide a fixed-length window across s while maintaining 26-letter frequency counts.

Q: What is the most efficient way to solve Find All Anagrams in a String?

Slide a fixed-length window across s while maintaining 26-letter frequency counts. This gives `O(n)` time complexity, and is a classic strings, sliding window, and hashmap problem.

Q: How do you solve Find All Anagrams in a String in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Find All Anagrams in a String solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Find All Anagrams in a String an easy or hard interview question?

Find All Anagrams in a String is generally rated **Medium**. It tests strings, sliding window, and hashmap, which are common coding-interview patterns.

Solution Walkthrough

1. Look for fixed-size windows

Every candidate substring must have exactly the same length as p.
That makes this a sliding-window problem rather than a variable-size window like minimum cover.

2. Recount each window from scratch

For every start index, build a fresh 26-letter frequency array for the substring and compare it with p.
This is correct, but it repeats almost all of the counting work between neighboring windows.

def find_anagrams(s, p):
    if len(p) > len(s):
        return []
    target = [0] * 26
    for char in p:
        target[ord(char) - ord("a")] += 1
    answer = []
    window_length = len(p)
    for start in range(len(s) - window_length + 1):
        counts = [0] * 26
        for index in range(start, start + window_length):
            counts[ord(s[index]) - ord("a")] += 1
        if counts == target:
            answer.append(start)
    return answer

3. Slide one fixed-size window across s

Count p once, count the first window once, then update the window in O(1) per move.
Because the alphabet size is fixed at 26, comparing the two count arrays is still constant time.

4. Update counts incrementally

Add the new right character, remove the old left character, and compare the arrays.
Every window is visited exactly once.

def find_anagrams(s, p):
    if len(p) > len(s):
        return []
    target = [0] * 26
    window = [0] * 26
    for index in range(len(p)):
        target[ord(p[index]) - ord("a")] += 1
        window[ord(s[index]) - ord("a")] += 1
    answer = []
    if window == target:
        answer.append(0)
    for right in range(len(p), len(s)):
        window[ord(s[right]) - ord("a")] += 1
        window[ord(s[right - len(p)]) - ord("a")] -= 1
        if window == target:
            answer.append(right - len(p) + 1)
    return answer

5. Dry run / sliding-window trace

Trace s = "abab", p = "ab".

window	indices	counts match?	answer
`"ab"`	`[0,1]`	yes	`[0]`
slide right -> `"ba"`	`[1,2]`	yes	`[0,1]`
slide right -> `"ab"`	`[2,3]`	yes	`[0,1,2]`

Only one character enters and one leaves on each step, so recomputing the full frequency table is unnecessary.

6. Final solution and complexity

A fixed-size sliding window with 26-letter frequency arrays finds every anagram in linear time and constant extra space.

def find_anagrams(s: str, p: str) -> list[int]:
    if len(p) > len(s):
        return []
    target = [0] * 26
    window = [0] * 26
    for index in range(len(p)):
        target[ord(p[index]) - ord("a")] += 1
        window[ord(s[index]) - ord("a")] += 1
    answer: list[int] = []
    if window == target:
        answer.append(0)
    for right in range(len(p), len(s)):
        window[ord(s[right]) - ord("a")] += 1
        window[ord(s[right - len(p)]) - ord("a")] -= 1
        if window == target:
            answer.append(right - len(p) + 1)
    return answer

Find All Anagrams in a String – Solution & Complexity

Solution Walkthrough

1. Look for fixed-size windows

2. Recount each window from scratch

3. Slide one fixed-size window across s

4. Update counts incrementally

5. Dry run / sliding-window trace

6. Final solution and complexity

FAQ

What is the time and space complexity of Find All Anagrams in a String?

What is the most efficient way to solve Find All Anagrams in a String?

How do you solve Find All Anagrams in a String in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Find All Anagrams in a String an easy or hard interview question?

See also