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. Given the following Python code implementing the optimal approach for longest consecutive sequence, what is the value of max_len returned when the input is [1, 9, 3, 10, 4, 20, 2]?

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in num_set:
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_len = max(max_len, length)
    return max_len

easy

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Identify sequence starts

   Numbers without predecessor: 1 (0 not in set), 9 (8 not in set), 20 (19 not in set).

2. Step 2: Trace sequences from starts

   From 1: sequence is 1,2,3,4 -> length 4; from 9: 9,10 -> length 2; from 20: 20 -> length 1. Max length is 4.

3. Step 3: Re-examine carefully

   Check if 1,2,3,4 is the longest. Actually, 1,2,3,4 is length 4, but 1,2,3,4,5 is not present. So max length is 4.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Longest consecutive sequence length is 4 [OK]

Hint: Only count sequences starting at numbers without predecessor [OK]

Common Mistakes:

• Counting sequences from every number
• Off-by-one in length calculation
• Ignoring duplicates

2. Given an integer array and a target sum, you need to find the number of continuous subarrays whose sum equals the target. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use dynamic programming to store the count of subarrays ending at each index with sum equal to the target.

B. Use a sliding window technique to expand and shrink the window until the sum matches the target.

C. Maintain a running prefix sum and use a hash map to count how many prefix sums have occurred that satisfy the sum condition.

D. Check all possible subarrays using nested loops and sum each subarray to check if it equals the target.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting subarrays with sum equal to k, including negative numbers, so sliding window (which requires non-negative numbers) is not reliable.

2. Step 2: Identify the optimal approach

   Using prefix sums and a hash map allows constant-time lookups of how many prefix sums satisfy the condition, achieving O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window fails with negatives; brute force is O(n²); DP approach is not standard here. [OK]

Hint: Prefix sums + hash map handle negatives efficiently [OK]

Common Mistakes:

• Assuming sliding window works with negative numbers
• Thinking DP is needed for counting subarrays
• Believing brute force is optimal

3. Consider the following code snippet for finding the longest subarray with equal number of 0s and 1s. What is the value of max_length after processing the input [0, 1, 0, 1]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace prefix sums and first_occurrence updates.

   For input [0,1,0,1], prefix sums are: -1, 0, -1, 0 with offset indexing.

2. Step 2: Update max_length when prefix sum repeats.

   At i=1, prefix_sum=0 repeats at index -1 -> length=2; at i=3, prefix_sum=0 repeats again -> length=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Longest balanced subarray is entire array length 4 [OK]

Hint: Prefix sum repeats indicate balanced subarray [OK]

Common Mistakes:

• Off-by-one in length calculation
• Confusing prefix sum indexing
• Ignoring initial prefix sum at -1

4. The following code attempts to find the longest subarray with equal number of 0s and 1s. What is the subtle bug causing incorrect results on some inputs?

medium

A. Missing initialization of first_occurrence[offset] = -1 before the loop

B. Incorrect prefix_sum update: should add 1 for 0 and -1 for 1

C. Updating max_length before checking if prefix_sum exists in first_occurrence

D. Using -2 as initial value in first_occurrence instead of -1

Solution

1. Step 1: Check initialization of first_occurrence array.

   It must have first_occurrence[offset] = -1 to handle subarrays starting at index 0.

2. Step 2: Without this initialization, subarrays starting at index 0 are missed.

   This causes off-by-one errors and underestimation of max_length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug causes failure on inputs where balanced subarray starts at index 0 [OK]

Hint: Initialize prefix sum 0 at index -1 to avoid off-by-one [OK]

Common Mistakes:

• Not initializing prefix sum 0 index
• Confusing prefix sum updates
• Wrong initial values in array

5. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best