Problem Description

You are given two strings s and p. Your task is to find all the starting positions in string s where an anagram of string p begins.

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once. For example, "abc", "bca", and "cab" are all anagrams of each other.

You need to return a list of all starting indices where such anagrams of p can be found in s. The indices can be returned in any order.

For example:

• If s = "cbaebabacd" and p = "abc", the anagrams of p found in s are "cba" starting at index 0 and "bac" starting at index 6. So the output would be [0, 6].
• If s = "abab" and p = "ab", the anagrams of p found in s are "ab" starting at index 0, "ba" starting at index 1, and "ab" starting at index 2. So the output would be [0, 1, 2].

The key insight is that you're looking for substrings of s that have the same length as p and contain exactly the same characters with the same frequencies as p, just potentially in a different order.

Intuition

To find all anagrams of p in string s, we need to check if substrings of s have the same character frequencies as p. The naive approach would be to check every possible substring of length len(p) in s, but this would involve repeatedly counting characters for overlapping windows.

The key observation is that consecutive windows of the same size overlap significantly - they differ by only one character. When we slide from one window to the next, we're essentially removing one character from the left and adding one character from the right.

This naturally leads us to a sliding window approach with frequency counting. Instead of recounting all characters for each window, we can:

1. Start with a window of size len(p)
2. Keep track of character frequencies in the current window
3. As we slide the window one position to the right, update the frequency count by:
   • Adding the new character that enters the window on the right
   • Removing the character that exits the window on the left

To check if a window is an anagram, we simply compare the frequency map of the current window with the frequency map of p. If they're identical, we've found an anagram.

The efficiency comes from the fact that updating the frequency map for each new window position takes O(1) time (just two updates), rather than O(n) time to recount everything. We're essentially maintaining a "running count" of characters as we slide through the string, which is much more efficient than starting fresh for each position.

Solution Approach

The solution implements a sliding window technique with character frequency counting using Python's Counter data structure.

Step 1: Initial Setup

m, n = len(s), len(p)
ans = []
if m < n:
    return ans

First, we get the lengths of both strings. If s is shorter than p, no anagram is possible, so we return an empty list immediately.

Step 2: Create Frequency Maps

cnt1 = Counter(p)
cnt2 = Counter(s[: n - 1])

• cnt1 stores the character frequencies of string p - this remains constant throughout
• cnt2 is initialized with the first n-1 characters of s (not the full window yet)

Step 3: Sliding Window Process

for i in range(n - 1, m):
    cnt2[s[i]] += 1
    if cnt1 == cnt2:
        ans.append(i - n + 1)
    cnt2[s[i - n + 1]] -= 1

The loop starts from index n-1 and goes through the entire string s:

1. Add the rightmost character: cnt2[s[i]] += 1 completes the window of size n by adding the character at position i

2. Check for anagram: if cnt1 == cnt2 compares the two frequency maps. If they're identical, we've found an anagram. The starting index of this window is i - n + 1, which we add to our result list

3. Remove the leftmost character: cnt2[s[i - n + 1]] -= 1 prepares for the next iteration by removing the leftmost character of the current window

Why this works:

• The window maintains exactly n characters at all times (after the first addition in each iteration)
• By adding one character on the right and removing one on the left, we efficiently slide the window
• Python's Counter comparison checks if two dictionaries have identical key-value pairs, perfect for anagram detection
• The time complexity is O(m) where m = len(s), as we visit each character once and Counter comparison is O(1) for fixed alphabet size

Example Walkthrough

Let's trace through a small example with s = "cbaebabacd" and p = "abc".

Initial Setup:

• m = 10 (length of s), n = 3 (length of p)
• cnt1 = {'a': 1, 'b': 1, 'c': 1} (frequency map of "abc")
• cnt2 = {'c': 1, 'b': 1} (frequency map of first 2 characters "cb")

Sliding Window Process:

Iteration 1 (i = 2):

• Add s[2] = 'a': cnt2 = {'c': 1, 'b': 1, 'a': 1}
• Window contains "cba" (indices 0-2)
• Compare: cnt1 == cnt2? YES! Both have {'a': 1, 'b': 1, 'c': 1}
• Add starting index: 2 - 3 + 1 = 0 to result
• Remove s[0] = 'c': cnt2 = {'c': 0, 'b': 1, 'a': 1}

Iteration 2 (i = 3):

• Add s[3] = 'e': cnt2 = {'c': 0, 'b': 1, 'a': 1, 'e': 1}
• Window contains "bae" (indices 1-3)
• Compare: cnt1 == cnt2? NO (cnt2 has 'e', no 'c')
• Remove s[1] = 'b': cnt2 = {'c': 0, 'b': 0, 'a': 1, 'e': 1}

Iteration 3 (i = 4):

• Add s[4] = 'b': cnt2 = {'c': 0, 'b': 1, 'a': 1, 'e': 1}
• Window contains "aeb" (indices 2-4)
• Compare: cnt1 == cnt2? NO
• Remove s[2] = 'a': cnt2 = {'c': 0, 'b': 1, 'a': 0, 'e': 1}

Skip to Iteration 7 (i = 8):

• After iterations 4-6, cnt2 = {'b': 1, 'a': 1, 'c': 0}
• Add s[8] = 'c': cnt2 = {'b': 1, 'a': 1, 'c': 1}
• Window contains "bac" (indices 6-8)
• Compare: cnt1 == cnt2? YES! Both have {'a': 1, 'b': 1, 'c': 1}
• Add starting index: 8 - 3 + 1 = 6 to result
• Remove s[6] = 'b': cnt2 = {'b': 0, 'a': 1, 'c': 1}

Final Result: [0, 6] - anagrams found at indices 0 and 6.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m) where m is the length of string s.

• Creating Counter(p) takes O(n) time where n is the length of string p.
• Creating Counter(s[:n-1]) takes O(n) time.
• The main loop runs m - n + 1 times (from index n-1 to m-1).
• Inside the loop:
  • Adding/incrementing a character to cnt2: O(1)
  • Comparing two Counter objects cnt1 == cnt2: O(1) on average since both counters have at most 26 keys (lowercase English letters)
  • Decrementing a character from cnt2: O(1)
  • Appending to result list: O(1)
• Total: O(n) + O(n) + O(m - n + 1) × O(1) = O(m)

Space Complexity: O(1) or O(n) depending on interpretation.

• cnt1 stores at most 26 key-value pairs (for lowercase English letters): O(1)
• cnt2 stores at most 26 key-value pairs: O(1)
• The result list ans can contain at most m - n + 1 indices in the worst case: O(m - n + 1) = O(m)
• If we consider only auxiliary space (excluding output), the space complexity is O(1) since the Counter objects are bounded by the alphabet size.
• If we include the output space, the space complexity is O(m) in the worst case.

Common Pitfalls

1. Not Cleaning Up Zero-Count Entries in Counter

The Pitfall: When decrementing character counts in the sliding window, leaving entries with zero counts in the Counter can cause incorrect comparisons. For example:

• Counter({'a': 1, 'b': 0}) is NOT equal to Counter({'a': 1})
• This leads to missing valid anagrams because the equality check pattern_counter == window_counter fails even when the actual character frequencies match

Example of the Bug:

# Buggy version - doesn't remove zero-count entries
for i in range(p_length - 1, s_length):
    window_counter[s[i]] += 1
    if pattern_counter == window_counter:
        result.append(i - p_length + 1)
    window_counter[s[i - p_length + 1]] -= 1  # Leaves zero counts!

The Solution: Always remove entries when their count reaches zero:

left_char = s[i - p_length + 1]
window_counter[left_char] -= 1
if window_counter[left_char] == 0:
    del window_counter[left_char]  # Critical: remove zero-count entries

2. Incorrect Window Initialization

The Pitfall: Initializing the window with the full p_length characters instead of p_length - 1 breaks the sliding window logic:

# Wrong: Starting with full window
window_counter = Counter(s[:p_length])  # This is incorrect!

This causes the first iteration to have p_length + 1 characters in the window, leading to incorrect results.

The Solution: Initialize with p_length - 1 characters, then complete the window in the loop:

# Correct: Start with p_length - 1 characters
window_counter = Counter(s[:p_length - 1])
# Then in the loop, add one character to complete the window

3. Off-by-One Errors in Index Calculation

The Pitfall: Incorrectly calculating the starting index of the anagram window:

# Common mistakes:
result.append(i - p_length)      # Wrong: off by one
result.append(i - n)              # Wrong: using wrong variable
result.append(i)                  # Wrong: using end index instead of start

The Solution: The correct formula is i - p_length + 1 where:

• i is the current (rightmost) position in the window
• p_length is the window size
• Adding 1 adjusts for the 0-based indexing

Visual Example:

s = "cbaebabacd", p = "abc" (length 3)
When i = 2: window is s[0:3] = "cba"
Starting index = 2 - 3 + 1 = 0 ✓