Workspace

Problem workspace

3 day streakD

Find All Anagrams in a String

MediumSliding WindowFixed windows

The challenge

Return every start index where a substring of s is an anagram of pattern. Anagrams have exactly the same character multiplicities.

Strings contain lowercase English letters. The pattern is nonempty. Indices are zero-based.

Example

s = cbaebabacd, pattern = abc → [0, 6].

Use the walkthrough below to inspect the input and each state change.

See Anagram windows, step by step

Expand, shrink, and inspect the window state.

10 elements · zero-based indicespattern = abc
Sliding window over 10 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1c0b1a2e3b4a5b6a7c8d9
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 20

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

[]
View exact input

Input: ["c","b","a","e","b","a","b","a","c","d"] · pattern = abc

Current window is empty.

Put it into code

Keep a frequency vector for a window of pattern.length characters. Comparing 26 counters is constant work for this alphabet.

Indices are zero-based. C++ uses C++17 or later.

def find_anagrams(s, pattern):
    # Lowercase English letters; pattern is nonempty.
    need, window = [0] * 26, [0] * 26
    for char in pattern:
        need[ord(char) - ord('a')] += 1
    answer, k = [], len(pattern)
    for right, char in enumerate(s):
        window[ord(char) - ord('a')] += 1
        if right >= k:
            window[ord(s[right - k]) - ord('a')] -= 1
        if right >= k - 1 and window == need:
            answer.append(right - k + 1)
    return answer

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap