MediumHash TableStringSliding Window

Find All Anagrams in a String

1 approach, code in every language

Given two strings s and p, report the starting index of every substring of s that is an anagram of p, meaning it uses exactly the same letters with the same multiplicities as p.

The indices can be returned in any order, and an empty list is valid when no such substring exists.

Example 1

Input: s = "cbaebabacd", p = "abc"

Output: [0, 6]

The substrings starting at index 0 ("cba") and index 6 ("bac") are rearrangements of "abc".

Example 2

Input: s = "abab", p = "ab"

Output: [0, 1, 2]

Each window "ab", "ba", and "ab" is an anagram of "ab".

Constraints

1 <= s.length, p.length <= 3 * 10^4
s and p consist of lowercase English letters.

Fixed-width window with letter counts

Slide a window of length |p| across s, maintaining a 26-slot letter tally, and record every position where that tally matches p's tally.

Loading animation…

Intuition

An anagram is fully described by how many of each letter it contains, so two strings are anagrams exactly when their letter-count vectors are equal. Because the window is a fixed length, each step adds one letter on the right and removes one on the left, updating the tally in constant time. Comparing the window tally against p's tally at each valid position pinpoints all anagram starts in a single pass.

Algorithm walkthrough

1Build a 26-length count of p and a matching count for the first window of s.
2Slide the window one character at a time: add the entering character and, once the window is full length, subtract the leaving character.
3Whenever the window has reached the length of p, compare its count vector with p's count vector.
4If the two vectors are identical, append the window's starting index to the results.
5After the final position is checked, return the collected indices.

Implementation

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        if len(p) > len(s):
            return result
        need = [0] * 26
        window = [0] * 26
        base = ord('a')
        for c in p:
            need[ord(c) - base] += 1
        for i, ch in enumerate(s):
            window[ord(ch) - base] += 1
            if i >= len(p):
                window[ord(s[i - len(p)]) - base] -= 1
            if i >= len(p) - 1 and window == need:
                result.append(i - len(p) + 1)
        return result

Time

O(n)

Space

O(1)

Both count arrays are fixed at 26 entries regardless of input size.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Mosaic Bundle Positions is our own problem on the technique behind Find All Anagrams in a String: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free