Find All Anagrams in a String

📋

Problem

Imagine you are analyzing a large text to find all places where a certain word's letters appear in any order, like finding all jumbled versions of 'listen' in a book.

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. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

1 ≤ s.length, p.length ≤ 10^5s and p consist of lowercase English letters

Edge cases: p longer than s → empty outputs and p are identical → output [0]s or p is a single character → output all indices where characters match

</>

IDE

def findAnagrams(s: str, p: str) -> list:public List<Integer> findAnagrams(String s, String p)vector<int> findAnagrams(string s, string p)function findAnagrams(s, p)

def findAnagrams(s, p):
    # Write your solution here
    pass

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> findAnagrams(string s, string p) {
    // Write your solution here
    return {};
}

function findAnagrams(s, p) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Missing some valid anagram indicesSliding window frequency counts not updated correctly when window moves✅ Update frequency counts by decrementing count of outgoing char and incrementing incoming char each step

Wrong: Returns non-empty output when p is longer than sNo length check before processing substrings✅ Add early return if len(p) > len(s) to return empty list

Wrong: Misses overlapping anagrams due to greedy skippingSkipping indices after finding one anagram instead of checking every window✅ Check every window of length p without skipping any indices

Wrong: Incorrect matches due to comparing only character sets, not countsFrequency comparison ignores exact counts, only checks presence✅ Compare full frequency maps or arrays for exact count equality

Wrong: TLE on large inputsBrute force approach checking all substrings with full frequency recomputation✅ Use sliding window with incremental frequency updates and match count optimization

✓

Test Cases

Try testing your code on empty and single-character inputs to handle base cases.

Consider tricky inputs with repeated characters and overlapping anagrams.

Think about how to optimize your solution to run efficiently on very large inputs.

t1_01basic

Input{"s":"cbaebabacd","p":"abc"}

Expected[0,6]

⏱ Performance - must finish in 2000ms

The substring with start index 0 is 'cba', an anagram of 'abc'. The substring with start index 6 is 'bac', also an anagram of 'abc'.

💡 Consider using a sliding window to check substrings of length equal to p.

💡 Track character frequencies in p and compare with the current window's frequencies.

💡 Update counts incrementally as the window slides instead of recomputing from scratch.

Why it failed: Output missing or incorrect indices of anagrams; likely frequency counts or window updates are wrong. Fix by ensuring frequency maps are updated correctly when sliding the window.

✓ Correctly identifies all start indices of anagrams using frequency tracking.

t1_02basic

Input{"s":"abab","p":"ab"}

Expected[0,1,2]

⏱ Performance - must finish in 2000ms

Substrings 'ab' at indices 0, 2 and 'ba' at index 1 are all anagrams of 'ab'.

💡 Check every substring of length equal to p for matching frequency counts.

💡 Use a sliding window and update counts as you move to avoid recomputing.

💡 Compare frequency maps or use a match count to detect anagrams efficiently.

Why it failed: Missed some valid anagram indices; likely frequency comparison or window sliding logic is incomplete. Fix by correctly updating counts and checking all windows.

✓ All anagram start indices found correctly with efficient frequency tracking.

t2_01edge

Input{"s":"","p":"a"}

Expected[]

⏱ Performance - must finish in 2000ms

Empty string s means no substrings, so no anagrams possible.

💡 Consider what happens when s is empty.

💡 Check if your code handles zero-length input gracefully.

💡 Return an empty list immediately if s is shorter than p.

Why it failed: Code crashes or returns non-empty output for empty s; fix by adding a check for s length before processing.

✓ Handles empty s input correctly by returning empty list.

t2_02edge

Input{"s":"a","p":"a"}

Expected[0]

⏱ Performance - must finish in 2000ms

Single character strings that match produce one anagram at index 0.

💡 Test the smallest non-empty input where s and p are single characters.

💡 Ensure your frequency comparison works for single-character strings.

💡 Return [0] if s equals p.

Why it failed: Fails to detect single-character anagram; fix by handling single-character frequency comparison correctly.

✓ Correctly identifies single-character anagram at index 0.

t2_03edge

Input{"s":"abc","p":"abcd"}

Expected[]

⏱ Performance - must finish in 2000ms

p longer than s means no substrings of length p exist, so no anagrams.

💡 Check if your code handles cases where p is longer than s.

💡 Return empty list immediately if p length > s length.

💡 Avoid unnecessary processing when substring length is impossible.

Why it failed: Returns non-empty output or crashes when p is longer than s; fix by adding length check before processing.

✓ Correctly returns empty list when p is longer than s.

t3_01corner

Input{"s":"aaaaaaaaaa","p":"aaa"}

Expected[0,1,2,3,4,5,6,7]

⏱ Performance - must finish in 2000ms

All substrings of length 3 are 'aaa', matching p exactly.

💡 Consider cases where all characters are identical.

💡 Check if your frequency tracking handles repeated characters correctly.

💡 Ensure sliding window updates counts correctly without resetting.

Why it failed: Misses some indices or returns duplicates; fix by correctly updating frequency counts and sliding window boundaries.

✓ Correctly finds all overlapping anagrams with repeated characters.

t3_02corner

Input{"s":"abacbabc","p":"abc"}

Expected[1,2,3,5]

⏱ Performance - must finish in 2000ms

Anagrams of 'abc' appear starting at indices 1 ('bac'), 2 ('acb'), 3 ('cba'), and 5 ('abc').

💡 Beware of greedy approaches that skip indices after finding one anagram.

💡 Check every window of length p, do not skip windows.

💡 Use a sliding window with frequency counts to detect all anagrams.

Why it failed: Greedy skipping causes missed anagrams; fix by checking every window without skipping after matches.

✓ All anagrams found by checking every window correctly.

t3_03corner

Input{"s":"abcabcabc","p":"aabbcc"}

Expected[0,1,2,3]

⏱ Performance - must finish in 2000ms

No substring of length 6 matches the frequency of 'aabbcc' exactly.

💡 Check that your frequency comparison requires exact counts, not just presence.

💡 Avoid confusing 0/1 occurrences with unbounded counts.

💡 Ensure frequency maps match counts exactly, not just character sets.

Why it failed: Incorrectly returns matches due to ignoring exact counts; fix by comparing full frequency counts exactly.

✓ Correctly returns empty list when no exact frequency match exists.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n) or O(n*k) solution to complete within 2 seconds.

💡 Brute force O(n*m) will time out for large inputs.

💡 Use sliding window with frequency maps and incremental updates.

💡 Optimize to O(n) by tracking matches with counters instead of full map comparisons.

Why it failed: TLE due to brute force or inefficient frequency comparisons; fix by implementing sliding window with incremental frequency updates.

✓ Solution runs efficiently within time limits using optimized sliding window approach.

Practice

1. You need to find the length of the longest substring in a string that contains at most k distinct characters. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window with a frequency map or ordered dictionary to dynamically track distinct characters

B. Brute force checking of all substrings and counting distinct characters each time

C. Dynamic programming with a 2D table storing substring states

D. Greedy approach that expands the substring until distinct characters exceed k, then resets

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest substring with at most k distinct characters, which suggests a variable-size window approach.

2. Step 2: Identify optimal approach

   Sliding window with a frequency map or ordered dictionary efficiently tracks distinct characters and adjusts window size in O(n) time, unlike brute force or DP.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with frequency map is standard for this problem [OK]

Hint: Sliding window with frequency map solves this in O(n) [OK]

Common Mistakes:

• Thinking brute force or DP is efficient enough
• Assuming greedy reset works without shrinking window properly

2. You are given a string and need to find the length of the longest substring where no character repeats. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings and verifying uniqueness by sorting each substring

B. Sliding window with a hash map tracking the last seen index of each character to dynamically adjust the window

C. Dynamic programming by storing longest substring lengths ending at each index without duplicates

D. Greedy approach by always extending the substring until a duplicate is found, then restarting from next character

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest substring without repeating characters, which suggests a variable-size window to track unique characters efficiently.

2. Step 2: Evaluate approaches

   Brute force and greedy approaches either have high time complexity or fail to adjust the window correctly. Dynamic programming is not straightforward here. The sliding window with a hash map efficiently tracks last seen indices and adjusts the window in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with index tracking is the known optimal pattern [OK]

Hint: Sliding window with index map -> O(n) solution [OK]

Common Mistakes:

• Confusing greedy restart with sliding window
• Using DP without clear state definition

3. Identify the bug in the following code snippet for the Maximum Points You Can Obtain from Cards problem:

medium

A. Line 7: Loop range should start from k instead of window_size.

B. Line 4: Incorrect initial sum calculation; should sum last k elements instead of first window_size.

C. Line 9: The condition should be current_sum > min_subarray_sum instead of <.

D. Line 3: Incorrect calculation of window_size; should be n - k instead of k.

Solution

1. Step 1: Understand window size meaning

   The window represents the subarray to exclude, which must be length n - k, not k.

2. Step 2: Identify impact of wrong window size

   Using k as window size causes the algorithm to exclude wrong subarray length, leading to incorrect results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct window size is n - k for the sliding window [OK]

Hint: Window size must be n - k, not k [OK]

Common Mistakes:

• Confusing window size with k instead of n-k
• Incorrect loop boundaries
• Wrong comparison operator in min update

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 problem is modified so that the array can contain negative numbers as well as positive numbers. Which of the following statements about applying the sliding window approach to find the minimum size subarray sum ≥ target is true?

hard

A. Sliding window fails because negative numbers can cause the sum to decrease unpredictably, breaking the monotonic window property

B. Sorting the array first allows sliding window to work correctly with negatives

C. Sliding window still works unchanged because the sum can be adjusted dynamically

D. Prefix sums with binary search is invalid because sums can be negative

Solution

1. Step 1: Understand sliding window assumptions

   Sliding window relies on sums increasing as right pointer moves forward and shrinking from left to reduce sum, which requires all positive numbers.

2. Step 2: Effect of negative numbers

   Negative numbers can decrease sum inside the window unpredictably, so shrinking or expanding window does not guarantee monotonic sum changes, breaking the approach.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window requires non-negative numbers for correctness [OK]

Hint: Negative numbers break sliding window monotonic sum property [OK]

Common Mistakes:

• Assuming sliding window works with negatives
• Thinking sorting fixes contiguous subarray sums
• Believing prefix sums binary search fails with negatives