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 - LeetCode Solution

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

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. Using a sliding window of size k, the algorithm updates the frequency counts incrementally as the window moves, avoiding recomputation from scratch.

Optimal Approach

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.

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

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

8for right, ch in enumerate(s):
  window[ch] += 1
  if right >= k:
      left_ch = s[right - k]
      window[left_ch] -= 1
      if window[left_ch] == 0:
          del window[left_ch]

Objective

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.

Key Insight

Incrementally updating the window frequency counter as the window slides avoids recomputing counts from scratch. Removing characters that fall out of the window and deleting zero-count entries keeps the window counter clean and comparable to the need counter. This incremental maintenance is the core efficiency gain of the sliding window approach.

Interview Quick-Check

Core Logic

Increment the count for the new character entering the window and decrement the count for the character leaving the window to maintain accurate frequency counts.

State & Boundaries

Only remove the left character from the window when the window size exceeds k to maintain a fixed-size window.

Common Pitfalls & Bugs

Failing to delete characters with zero count from the window counter causes incorrect equality checks with the need counter.

Complexity

Each character is added and removed at most once, ensuring O(n) time complexity.

3

Detect Anagram Matches and Record Start Indices

18if window == need:
19    res.append(right - k + 1)

Objective

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

Key Insight

Equality of the two counters guarantees the current window is an anagram of p. Recording the start index (right - k + 1) captures the position of the valid substring. This check is performed at every step after the window is updated, ensuring all anagrams are found.

Interview Quick-Check

Core Logic

Comparing the window and need counters directly detects anagram matches without additional computation.

State & Boundaries

The start index is calculated as right - k + 1 to reflect the beginning of the current window.

Common Pitfalls & Bugs

Not performing the equality check after every window update can cause missed matches.

4

Return the List of Anagram Start Indices

21	`return res`

Objective

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

Key Insight

After processing the entire string s with the sliding window, the result list contains all valid start indices. Returning this list completes the solution.

Interview Quick-Check

Core Logic

Returning the result list provides the final answer as required by the problem.

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.

Line 3 Core

need = Counter(p)

Create a frequency counter for characters in p.

Precomputing the frequency of p's characters enables constant-time comparison with the sliding window's frequency map, which is essential for efficient anagram detection.

Line 9 Core

window[ch] += 1

Increment the count of the current character in the window counter.

Adding the new character to the window frequency map maintains an accurate count of characters in the current window, enabling correct anagram detection.

Line 13 Core

window[left_ch] -= 1

Decrement the count of the leftmost character in the window counter.

Removing the leftmost character's count keeps the window frequency map accurate and consistent with the current window substring.

Line 4 Core

window = Counter()

Initialize an empty frequency counter for the sliding window.

This counter tracks the frequency of characters in the current window of s, allowing incremental updates and comparisons to the target frequency.

Line 11 Core

if right >= k:

Check if the window size exceeds k to remove the leftmost character.

Maintaining a fixed window size requires removing the character that falls out as the window slides forward.

Line 19 Core

res.append(right - k + 1)

Append the start index of the current anagram to the result list.

Recording the start index upon detection ensures all valid anagram positions are collected for the final output.

Line 8 Standard

for right, ch in enumerate(s):

Iterate over s with index and character to expand the sliding window.

Enumerating s allows the window to move forward one character at a time, updating the frequency counts accordingly.

Line 12 Standard

left_ch = s[right - k]

Identify the character that is leaving the window.

Knowing which character to decrement is necessary to update the window frequency map correctly.

Line 6 Standard

k = len(p)

Store the length of p as the fixed window size k.

Defining the window size upfront is critical for maintaining a sliding window of the correct length over s.

Line 5 Standard

res = []

Initialize the result list to store start indices of anagrams.

This list accumulates all valid starting positions, enabling the function to return all matches after processing.

Line 21 Standard

return res

Return the list of all starting indices of anagrams found.

Returning the accumulated results completes the function, providing the required output.

Line 16 Basic

del window[left_ch]

End of the conditional block for window shrinking.

This line marks the logical end of the window size maintenance, ensuring the window remains fixed size.

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?

Because an anagram requires the exact same count of each character. If the frequency counters match, the substring contains the same characters in the same quantities as p, confirming it is an anagram.

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)`

8	`for right, ch in enumerate(s):`
9	`window[ch] += 1`
11	`if right >= k:`
12	`left_ch = s[right - k]`
13	`window[left_ch] -= 1`
15	`if window[left_ch] == 0:`
16	`del window[left_ch]`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Frequency Counters and Result List

Expand Sliding Window and Maintain Frequency Counts

Detect Anagram Matches and Record Start Indices

Return the List of Anagram Start Indices

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.