How do you solve Find All Anagrams in a String?

Use a sliding window of size k = len(p) over s. Maintain two frequency counters: one for p (need) and one for the current window (window). For each step, add the new character to window and remove the character that slides out. When window equals need, record the start index. This approach runs in O(n) time with O(1) space for fixed alphabet size.

What pattern does Find All Anagrams in a String use?

The Pattern: Sliding Window (Fixed-Size Frequency Matching) The Heuristic: When searching for all substrings of fixed length that satisfy a frequency-based condition, maintain a sliding window with incremental updates to frequency counts and compare to the target frequency map to detect matches efficiently.

Find All Anagrams in a String — Sliding Window

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

O(n). Each character in s is visited once when added to the window and once when removed, resulting in a linear pass. Frequency comparisons are O(1) on average due to fixed alphabet size and efficient Counter equality checks.

Problem

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

1 ≤ s.length, p.length ≤ 3 * 10⁴
s and p consist of lowercase English letters.

Example

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

Output: [0, 6]

The substring starting at index 0 is "cba", which is an anagram of "abc". The substring starting at index 6 is "bac", which is also an anagram of "abc". The algorithm uses a sliding window of size equal to the length of p, maintaining a frequency count of characters in the current window and comparing it to the frequency count of p. When the counts match, the start index of the window is recorded.

Approach

Straightforward Solution

A brute-force approach would check every substring of s of length p, count characters, and compare to p's count. This results in O(n*k) time complexity, where n is the length of s and k is the length of p, which is inefficient for large inputs.

Core Observation

An anagram requires the frequency of each character in the substring to match exactly the frequency in p. This means the problem reduces to finding all substrings of s of length equal to p where the character counts match.

Path to Optimal

Preview

The key recognition signals are 'find all substrings of fixed length with matching character counts' and 'anagrams'. These indicate the Sliding Window pattern because the problem requires checking contiguous substrings of fixed size and comparing frequency counts efficiently…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a sliding window of size k = len(p) over s. Maintain two frequency counters: one for p (need) and one for the current window (window)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character in s is visited once when added to the window and once when removed, resulting in a linear pass. Frequency comparisons are O(1) on average due to fixed alphabet size and efficient Counter equality checks.

Space

O(1)

Frequency counters store counts for lowercase English letters only, a fixed size of 26, which is constant auxiliary space independent of input size.

Solution

Python

1class Solution:
  def findAnagrams(self, s: str, p: str) -> list[int]:
      need = Counter(p)
      window = Counter()
      res = []
      k = len(p)
7
      for right, ch in enumerate(s):
          window[ch] += 1
10
          if right >= k:
              left_ch = s[right - k]
              window[left_ch] -= 1
14
              if window[left_ch] == 0:
                  del window[left_ch]
17
          if window == need:
              res.append(right - k + 1)
20
      return res

Step-by-Step Solution

1

Initialize Frequency Counters and Result List

3need = Counter(p)
4window = Counter()
5res = []
6k = len(p)

Objective

To set up the frequency map for the target string p and prepare the sliding window frequency map and result container.

Key Insight

Precomputing the frequency of characters in p (need) allows constant-time comparison with the sliding window frequency map. Initializing an empty window counter and result list prepares the algorithm to track the current window's character counts and store valid start indices efficiently.

Interview Quick-Check

Core Logic

Using Counter for both need and window enables O(1) average-time frequency comparisons due to fixed alphabet size.

State & Boundaries

Setting k = len(p) defines the fixed window size, which is critical for sliding window correctness.

Common Pitfalls & Bugs

Forgetting to initialize the window counter or result list leads to runtime errors or incorrect results.

2

Expand Sliding Window and Maintain Frequency Counts

To iterate over s, expanding the window by adding the right character and shrinking it by removing the left character when the window exceeds size k.

3

Detect Anagram Matches and Record Start Indices

To compare the current window's frequency counter with the target frequency counter and record the start index when they match.

4

Return the List of Anagram Start Indices

To return the accumulated list of starting indices of all anagrams found in s.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 18 Critical

if window == need:

Check if the current window's frequency matches the target frequency.

This line embodies the algorithm's essence: comparing frequency counters directly detects anagrams in O(1) time on average, enabling efficient identification of valid substrings.

Line 15 Critical

if window[left_ch] == 0:

Delete the character from the window counter if its count reaches zero.

Deleting zero-count keys is critical because Counter equality checks consider keys; leaving zero-count keys would cause false mismatches, breaking the anagram detection.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why does comparing the frequency counters of the current window and the target string p guarantee that the substring is an anagram?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find All Anagrams in a String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find All Anagrams in a String drill

or drill a free problem

1	`class Solution:`
2	`def findAnagrams(self, s: str, p: str) -> list[int]:`
3	`need = Counter(p)`
4	`window = Counter()`
5	`res = []`
6	`k = len(p)`
7
8	`for right, ch in enumerate(s):`
9	`window[ch] += 1`
10
11	`if right >= k:`
12	`left_ch = s[right - k]`
13	`window[left_ch] -= 1`
14
15	`if window[left_ch] == 0:`
16	`del window[left_ch]`
17
18	`if window == need:`
19	`res.append(right - k + 1)`
20
21	`return res`

3	`need = Counter(p)`
4	`window = Counter()`
5	`res = []`
6	`k = len(p)`