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. What is the time complexity of the optimal prefix sum with hash map solution for finding the longest contiguous subarray with equal number of 0s and 1s, given an input array of length n?

medium

A. O(n) because each element is processed once with constant-time hash map operations

B. O(n) but with O(n²) space for storing all prefix sums

C. O(n log n) due to sorting or balanced tree operations in the hash map

D. O(n²) due to nested loops scanning subarrays

Solution

1. Step 1: Identify the single loop over the array

   The algorithm iterates once over n elements, updating prefix_sum and hash map.

2. Step 2: Confirm hash map operations are O(1) average

   Insertion and lookup in hash map are average O(1), so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is O(n²), no sorting involved, space is O(n) not O(n²) [OK]

Hint: Hash map lookups are average O(1), single pass over array [OK]

Common Mistakes:

• Confusing brute force O(n²) with optimal
• Assuming hash map is O(log n)
• Overestimating space complexity

2. What is the time complexity of the optimal dynamic programming solution that uses an array of hash maps to find the longest arithmetic subsequence length for an input array of size n?

medium

A. O(n^3) due to triple nested loops checking all subsequences

B. O(n^2 * W) where W is the range of possible differences

C. O(n log n) by sorting and binary searching differences

D. O(n^2) because each pair (i, j) is processed once with constant-time hash map operations on average

Solution

1. Step 1: Identify loops and operations

   The code has two nested loops over n, and inside uses hash map get/set which is average O(1).

2. Step 2: Confirm no hidden factors

   Difference range W does not affect complexity since hash maps handle keys efficiently; no sorting or extra loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two nested loops with O(1) hash ops -> O(n^2) time [OK]

Hint: Two nested loops with hash map ops yield O(n^2) time [OK]

Common Mistakes:

• Confusing difference range W as multiplicative factor
• Assuming triple nested loops from brute force
• Thinking sorting is involved

3. What is the time complexity of the optimal sliding window solution for finding the longest substring with at most two distinct characters, assuming the input string length is n?

medium

A. O(n²), because the inner while loop can run up to n times for each character.

B. O(n * k), where k is the number of distinct characters allowed (here k=2).

C. O(n log n), due to maintaining a balanced data structure for frequencies.

D. O(n), because each character is visited at most twice by the left and right pointers.

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 distinct_count > 2, also at most n times.

2. Step 2: Confirm total operations

   Each character is processed at most twice (once when right pointer visits, once when left pointer moves), so total operations are O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with two pointers is classic O(n) approach [OK]

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

Common Mistakes:

• Assuming nested loops multiply to O(n²)
• Confusing frequency map maintenance cost
• Thinking k affects complexity linearly

4. What is the time complexity of the optimal hash map frequency counting approach for finding the maximum number of k-sum pairs in an array of length n?

medium

A. O(n log n) due to sorting the array before processing

B. O(n) because each element is processed once with constant-time hash operations

C. O(n^2) because each element is compared with every other element

D. O(n) for iteration plus O(n) for building the frequency map, total O(2n) simplifies to O(n)

Solution

1. Step 1: Identify operations in hash map approach

   Each element is iterated once (O(n)) and frequency map updates are O(1) on average.

2. Step 2: Sum time components

   Building and updating frequency map is also O(n), so total is O(n) + O(n) = O(2n), which simplifies to O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity confirmed by single pass and constant-time map ops [OK]

Hint: Two O(n) steps sum to O(n), not O(n log n) [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops cause O(n^2)
• Ignoring constant factors in complexity

5. Suppose the input array can contain negative numbers and you want to find the number of subarrays whose sum equals k, but now you want to find the count of subarrays with sum divisible by k instead. Which modification to the optimal prefix sum with hash map approach correctly solves this variant?

hard

A. Use a sliding window approach since divisibility allows shrinking the window easily.

B. Track prefix sums modulo k and count frequencies of each remainder in a hash map.

C. Sort the array and use two pointers to find subarrays with sum divisible by k.

D. Use the original prefix sum approach without changes, as sum equals k and sum divisible by k are equivalent.

Solution

1. Step 1: Understand the problem variant

   We want subarrays where sum % k == 0, not sum == k.

2. Step 2: Modify prefix sums to track remainders

   Compute prefix sums modulo k and count how many prefix sums have the same remainder, since difference of prefix sums with same remainder is divisible by k.

3. Step 3: Use hash map to count frequencies of remainders

   Increment count by frequency of current remainder seen so far.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Sliding window fails with negatives; sorting breaks subarray continuity; original approach doesn't handle divisibility. [OK]

Hint: Use prefix sums modulo k and count remainder frequencies [OK]

Common Mistakes:

• Trying sliding window with negatives
• Ignoring modulo operation
• Assuming sum equals k and divisible by k are same