Find All Anagrams in a String

▶

Steps

setup

Initialize result list and check input lengths

Create an empty list to store results. Check if pattern length is greater than string length; if so, return empty list immediately.

💡 This step ensures we don't waste time processing impossible cases and prepares the result container.

Line:

res = []
if len(p) > len(s):
    return res

💡 Early termination avoids unnecessary work when pattern is longer than string.

setup

Initialize frequency arrays for pattern and sliding window

Create two arrays of length 26 initialized to zero to count character frequencies for pattern and current window in string.

💡 Frequency arrays allow constant-time updates and comparisons for each character a-z.

Line:

p_count = [0] * 26
s_count = [0] * 26

💡 Using fixed-size arrays indexed by character code is efficient for frequency tracking.

fill_row

Count frequencies of characters in pattern p

Iterate over each character in pattern p and increment its frequency count in p_count array.

💡 This step sets the target frequency counts that the sliding window will try to match.

Line:

for c in p:
    p_count[ord(c) - ord('a')] += 1

💡 Pattern frequency counts define the signature of an anagram to find.

fill_row

Initialize sliding window frequency with first p-length substring of s

Count frequencies of the first len(p) characters in s and store in s_count array.

💡 This sets the initial window to compare against the pattern frequencies.

Line:

for i in range(len(p)):
    s_count[ord(s[i]) - ord('a')] += 1

💡 Starting window frequency is ready for initial comparison.

compare

Count initial matches between pattern and window frequencies

Compare each character frequency in p_count and s_count arrays; increment matches count for each equal frequency.

💡 Matches count how many characters currently have matching frequencies, indicating potential anagram.

Line:

matches = 0
for i in range(26):
    if p_count[i] == s_count[i]:
        matches += 1

💡 Initial matches count shows how close the first window is to being an anagram.

compare

Start sliding window: check if initial window is an anagram

Since matches equals 26 (all characters match), append current left index 0 to result list.

💡 If all character frequencies match, the current window is an anagram starting at index l.

Line:

if matches == 26:
    res.append(l)

💡 An anagram is found at the start of the string.

insert

Slide window right: add character 'e' at index 3

Increment frequency count of character 'e' entering the window and update matches accordingly.

💡 Adding a new character changes the window frequency and may affect matches count.

Line:

index_r = ord(s[r]) - ord('a')
s_count[index_r] += 1
if s_count[index_r] == p_count[index_r]:
    matches += 1
elif s_count[index_r] == p_count[index_r] + 1:
    matches -= 1

💡 Adding a character not in pattern reduces matches count.

delete

Slide window right: remove character 'c' at index 0

Decrement frequency count of character 'c' leaving the window and update matches accordingly.

💡 Removing a character changes the window frequency and may restore or reduce matches count.

Line:

index_l = ord(s[l]) - ord('a')
s_count[index_l] -= 1
if s_count[index_l] == p_count[index_l]:
    matches += 1
elif s_count[index_l] == p_count[index_l] - 1:
    matches -= 1

💡 Removing a needed character reduces matches count further.

traverse

Move left pointer to 1

Increment left pointer to slide the window forward by one position.

💡 Moving the window forward prepares for the next iteration of frequency updates.

Line:

l += 1

💡 Window boundaries update to reflect the new substring under consideration.

insert

Slide window right: add character 'b' at index 4

Increment frequency count of character 'b' entering the window and update matches accordingly.

💡 Adding a character that is in the pattern may increase matches count.

Line:

index_r = ord(s[r]) - ord('a')
s_count[index_r] += 1
if s_count[index_r] == p_count[index_r]:
    matches += 1
elif s_count[index_r] == p_count[index_r] + 1:
    matches -= 1

💡 Adding an extra occurrence of a character beyond pattern frequency reduces matches.

delete

Slide window right: remove character 'b' at index 1

Decrement frequency count of character 'b' leaving the window and update matches accordingly.

💡 Removing a character may restore matches if frequency aligns with pattern frequency.

Line:

index_l = ord(s[l]) - ord('a')
s_count[index_l] -= 1
if s_count[index_l] == p_count[index_l]:
    matches += 1
elif s_count[index_l] == p_count[index_l] - 1:
    matches -= 1

💡 Removing extra occurrence restores a match for 'b'.

traverse

Move left pointer to 2

Increment left pointer to slide the window forward by one position.

💡 Moving the window forward prepares for the next iteration of frequency updates.

Line:

l += 1

💡 Window boundaries update to reflect the new substring under consideration.

insert

Slide window right: add character 'a' at index 5

Increment frequency count of character 'a' entering the window and update matches accordingly.

💡 Adding a character that matches pattern frequency may increase matches count.

Line:

index_r = ord(s[r]) - ord('a')
s_count[index_r] += 1
if s_count[index_r] == p_count[index_r]:
    matches += 1
elif s_count[index_r] == p_count[index_r] + 1:
    matches -= 1

💡 Adding extra occurrence of 'a' reduces matches count.

delete

Slide window right: remove character 'a' at index 2

Decrement frequency count of character 'a' leaving the window and update matches accordingly.

💡 Removing a character may restore matches if frequency aligns with pattern frequency.

Line:

index_l = ord(s[l]) - ord('a')
s_count[index_l] -= 1
if s_count[index_l] == p_count[index_l]:
    matches += 1
elif s_count[index_l] == p_count[index_l] - 1:
    matches -= 1

💡 Removing extra occurrence restores a match for 'a'.

traverse

Move left pointer to 3

Increment left pointer to slide the window forward by one position.

💡 Moving the window forward prepares for the next iteration of frequency updates.

Line:

l += 1

💡 Window boundaries update to reflect the new substring under consideration.

insert

Continue sliding window until index 6: add 'b', remove 'e', update matches

Add character 'b' at index 6 and remove character 'e' at index 3, updating frequencies and matches accordingly.

💡 Sliding window updates frequencies for entering and leaving characters to maintain accurate counts.

Line:

index_r = ord(s[r]) - ord('a')
s_count[index_r] += 1
if s_count[index_r] == p_count[index_r]:
    matches += 1
elif s_count[index_r] == p_count[index_r] + 1:
    matches -= 1
index_l = ord(s[l]) - ord('a')
s_count[index_l] -= 1
if s_count[index_l] == p_count[index_l]:
    matches += 1
elif s_count[index_l] == p_count[index_l] - 1:
    matches -= 1
l += 1

💡 Sliding window updates can restore matches and detect new anagrams.

compare

Check if current window at left=4 is an anagram

Since matches is not 26, do not append left index to results.

💡 Only when all character frequencies match do we record an anagram index.

Line:

if matches == 26:
    res.append(l)

💡 Current window is not an anagram.

insert

Slide window right: add character 'a' at index 7

Increment frequency count of character 'a' entering the window and update matches accordingly.

💡 Adding a character that matches pattern frequency may increase matches count.

Line:

index_r = ord(s[r]) - ord('a')
s_count[index_r] += 1
if s_count[index_r] == p_count[index_r]:
    matches += 1
elif s_count[index_r] == p_count[index_r] + 1:
    matches -= 1

💡 Adding extra occurrence of 'a' reduces matches count.

delete

Slide window right: remove character 'b' at index 4

Decrement frequency count of character 'b' leaving the window and update matches accordingly.

💡 Removing a character may restore matches if frequency aligns with pattern frequency.

Line:

index_l = ord(s[l]) - ord('a')
s_count[index_l] -= 1
if s_count[index_l] == p_count[index_l]:
    matches += 1
elif s_count[index_l] == p_count[index_l] - 1:
    matches -= 1

💡 Removing extra occurrence restores a match for 'b'.

compare

Move left pointer to 6 and check for anagram

Increment left pointer to 6. Since matches equals 26, append index 6 to results.

💡 When all character frequencies match, record the start index of the anagram.

Line:

l += 1
if matches == 26:
    res.append(l)

💡 An anagram is found starting at index 6.

def findAnagrams(s: str, p: str) -> list:
    res = []  # STEP 1
    if len(p) > len(s):  # STEP 1
        return res
    p_count = [0] * 26  # STEP 2
    s_count = [0] * 26  # STEP 2
    for c in p:  # STEP 3
        p_count[ord(c) - ord('a')] += 1
    for i in range(len(p)):  # STEP 4
        s_count[ord(s[i]) - ord('a')] += 1
    matches = 0  # STEP 5
    for i in range(26):  # STEP 5
        if p_count[i] == s_count[i]:
            matches += 1
    l = 0
    for r in range(len(p), len(s)):  # STEPS 6-20
        if matches == 26:  # STEP 6
            res.append(l)
        index_r = ord(s[r]) - ord('a')  # STEP 7,10,13,16,18
        s_count[index_r] += 1
        if s_count[index_r] == p_count[index_r]:
            matches += 1
        elif s_count[index_r] == p_count[index_r] + 1:
            matches -= 1
        index_l = ord(s[l]) - ord('a')  # STEP 8,11,14,16,19
        s_count[index_l] -= 1
        if s_count[index_l] == p_count[index_l]:
            matches += 1
        elif s_count[index_l] == p_count[index_l] - 1:
            matches -= 1
        l += 1  # STEP 9,12,15,16,20
    if matches == 26:  # STEP 20
        res.append(l)
    return res

if __name__ == '__main__':
    print(findAnagrams("cbaebabacd", "abc"))  # Output: [0, 6]

📊

Find All Anagrams in a String - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how frequency tracking and match counting work together to efficiently find all anagrams without redundant checks.

check

empty map

Result: []

insert

empty map

Result: []

insert

a→1

b→1

c→1

Result: []

insert

c→1

b→1

a→1

Result: []

check

a→1

b→1

c→1

Result: []

check

empty map

Result: [0]

increment

Lookup: e→ 1

e→1lookup

Result: [0]

decrement

Lookup: c→ 0

c→0lookup

Result: [0]

check

empty map

Result: [0]

increment

Lookup: b→ 2

b→2lookup

Result: [0]

decrement

Lookup: b→ 1

b→1lookup

Result: [0]

check

empty map

Result: [0]

increment

Lookup: a→ 2

a→2lookup

Result: [0]

decrement

Lookup: a→ 1

a→1lookup

Result: [0]

check

empty map

Result: [0]

increment

Lookup: b→ 2

b→2lookup

e→0

Result: [0]

check

empty map

Result: [0]

increment

Lookup: a→ 2

a→2lookup

Result: [0]

decrement

Lookup: b→ 1

b→1lookup

Result: [0]

check

empty map

Result: [0,6]

Key Takeaways

✓ Tracking frequency counts with fixed-size arrays allows constant-time updates and comparisons.

This insight is hard to see from code alone because the arrays abstract away character details, but visualization shows exact counts changing.

✓ The matches count efficiently summarizes how many characters currently match frequency, avoiding full array comparisons each step.

Understanding matches count is easier when watching it increment and decrement visually rather than reading conditional logic.

✓ Sliding the window by adding and removing characters updates frequencies and matches, enabling detection of anagrams without rechecking entire substrings.

Seeing each character enter and leave the window clarifies why the algorithm is efficient and how it maintains correctness.

Practice

1. Consider the following Python function implementing the optimal sliding window approach to find the minimum length of a subarray containing duplicate cards. What is the returned value when calling minimumCardPickup([1, 2, 3, 2])?

def minimumCardPickup(cards):
    last_seen = {}
    left = 0
    min_len = float('inf')
    for right, card in enumerate(cards):
        if card in last_seen and last_seen[card] >= left:
            left = last_seen[card] + 1
        last_seen[card] = right
        if right - left + 1 > 1:
            min_len = min(min_len, right - left + 1)
    return min_len if min_len != float('inf') else -1

easy

A. 2

B. 4

C. -1

D. 3

Solution

1. Step 1: Trace iterations for input [1, 2, 3, 2]

   Indices: 0->1, 1->2, 2->3, 3->2. At right=3, card=2 is duplicate with last_seen[2]=1 ≥ left=0, so left moves to 2.

2. Step 2: Calculate min_len updates

   Subarray lengths considered: from indices 1 to 3 is length 3, but after left update, window is from 2 to 3 length 2, min_len updated to 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimum subarray with duplicate '2' is [3,2] length 2 [OK]

Hint: Update left pointer on duplicate to shrink window [OK]

Common Mistakes:

• Off-by-one error in window length
• Not updating left pointer correctly

2. Consider the following code snippet implementing the optimal sliding window approach to check if s2 contains a permutation of s1. Given s1 = "ab" and s2 = "eidbaooo", what is the return value of the function?

easy

A. True

B. Raises an IndexError

C. False

D. Returns None

Solution

1. Step 1: Trace window expansion and counts

   For s1 = "ab", count array has counts for 'a' and 'b'. Sliding window moves over s2 = "eidbaooo". When window covers substring "ba" starting at index 3, window_count matches count, so formed == required.

2. Step 2: Confirm return value

   At this point, function returns True because a permutation of s1 is found in s2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Substring "ba" is a permutation of "ab" [OK]

Hint: Check substring "ba" matches "ab" permutation [OK]

Common Mistakes:

• Off-by-one errors in window size
• Forgetting to return True when formed == required

3. What is the time complexity of the optimal two-pointer sliding window solution for counting binary subarrays with a given sum, and why?

medium

A. O(n^2) because the inner while loop can run up to n times for each right pointer.

B. O(n) because each element is visited at most twice by the left and right pointers.

C. O(n log n) due to sorting or binary search steps involved.

D. O(n) but with O(n) auxiliary space for prefix sums or hash maps.

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once; the left pointer only moves forward when shrinking window, also at most n times.

2. Step 2: Confirm total operations

   Each element is added once and removed once from current_sum, so total operations are proportional to 2n = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer approach visits each element at most twice [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming inner while loop runs n times per right pointer iteration
• Confusing with prefix sum + hashmap space complexity
• Thinking sorting or binary search is involved

4. What is the time complexity of the sliding window approach for the Minimum Size Subarray Sum problem, and why might some candidates incorrectly think it is O(n²)?

medium

A. O(n log n) due to sorting or binary search inside the loop

B. O(n²) because of nested loops implied by two pointers

C. O(n) because each element is visited at most twice by left and right pointers

D. O(n) but with O(n) auxiliary space for prefix sums

Solution

1. Step 1: Identify pointer movements

   Right pointer moves forward once per iteration; left pointer moves forward only when shrinking window, each element visited at most twice.

2. Step 2: Analyze total operations

   Since both pointers only move forward, total operations are proportional to 2n = O(n), no nested repeated scanning.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window is classic O(n) approach [OK]

Hint: Two pointers each move forward once -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing prefix sums with sliding window
• Thinking auxiliary space affects time complexity

5. Suppose the input array can contain negative numbers as well as 0s and 1s. Which of the following statements about using the two-pointer sliding window approach to count subarrays with sum equal to goal is correct?

hard

A. Using prefix sums with a hash map is no longer valid when negative numbers are present.

B. The two-pointer sliding window approach still works correctly with minor modifications to handle negative numbers.

C. The two-pointer sliding window approach fails because the window sum can decrease unpredictably, causing infinite loops or incorrect counts.

D. Brute force is the only correct approach when negative numbers are allowed.

Solution

1. Step 1: Understand sliding window assumptions

   Sliding window relies on the sum increasing when expanding right pointer and decreasing when moving left pointer, which holds for non-negative numbers.

2. Step 2: Effect of negative numbers

   Negative numbers can cause sum to decrease when expanding right pointer, breaking monotonicity and causing infinite loops or incorrect counts.

3. Step 3: Alternative approaches

   Prefix sums with hash map still work with negatives; brute force is correct but inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sliding window fails with negative numbers due to non-monotonic sum [OK]

Hint: Sliding window requires non-negative elements for monotonic sum [OK]

Common Mistakes:

• Assuming sliding window works unchanged with negatives
• Thinking prefix sums with hash map fail with negatives
• Believing brute force is the only solution