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 are given an array of integers and a target sum k. You want to find the maximum number of pairs of elements whose sum equals k, with each element used at most once. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Sort the array and use a greedy approach to pick pairs from the start only.

B. Use nested loops to check all pairs and mark used elements.

C. Use a hash map to track frequencies of elements and find complements in one pass.

D. Use dynamic programming to count subsets that sum to k.

Solution

1. Step 1: Understand problem constraints

   The problem requires pairing elements to sum to k without reuse, maximizing count.

2. Step 2: Identify approach with linear time

   Using a hash map to track frequencies allows checking complements in O(1) per element, achieving O(n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map frequency counting is optimal and linear time [OK]

Hint: Hash map frequency counting solves pairing in O(n) [OK]

Common Mistakes:

• Assuming sorting alone solves pairing optimally
• Confusing subset sum DP with pair counting
• Using nested loops without optimization

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. The following code attempts to count the number of subarrays with bounded maximum using the optimal approach, but it contains a subtle bug:

def countAtMost(nums, bound):
    count = 0
    length = 0
    for num in nums:
        if num <= bound:
            length += 1
            count += length
        else:
            # Bug: missing reset of length here
            pass
    return count

def numSubarrayBoundedMax(nums, left, right):
    return countAtMost(nums, right) - countAtMost(nums, left - 1)

What is the bug in this code?

medium

A. The variable 'count' is not reset inside the loop, causing overcounting.

B. The function countAtMost should use max instead of length to track subarray size.

C. The 'length' variable is not reset to zero when encountering a number greater than bound.

D. The subtraction in numSubarrayBoundedMax should be reversed to avoid negative results.

Solution

1. Step 1: Understand the role of 'length'

   'length' tracks the length of the current valid subarray segment where elements ≤ bound.

2. Step 2: Identify the bug

   When an element > bound is encountered, 'length' must reset to 0 to avoid counting invalid subarrays. The code misses this reset, causing overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting 'length' on invalid elements is essential [OK]

Hint: Reset 'length' to zero on elements > bound [OK]

Common Mistakes:

• Forgetting to reset length
• Incorrect subtraction order
• Misusing count variable

4. The following code attempts to implement summaryRanges but has a subtle bug. Which line contains the bug?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

medium

A. Line 7: The inner while loop condition misses the last element in some cases.

B. Line 4: Not checking if input list is empty causes crash on empty input.

C. Line 11: Updating start to end + 1 might skip elements if end is not updated correctly.

D. Line 9: Always appending 'start->end' even when start == end causes incorrect output for single elements.

Solution

1. Step 1: Identify output format issue

   When start == end, the code appends 'num->num' instead of just 'num', which is incorrect per problem spec.

2. Step 2: Confirm other lines are correct

   Inner loop condition and start update are correct; empty input handling is not shown but not the subtle bug here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single element ranges must be output as single numbers, not ranges [OK]

Hint: Single element ranges output as 'num', not 'num->num' [OK]

Common Mistakes:

• Appending 'start->end' even when start == end
• Off-by-one in inner loop
• Skipping last range due to loop condition

5. Suppose the problem changes: now you want the longest substring with at most two distinct characters, but characters can be reused infinitely many times and the input string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Maintain a sliding window with frequency counts but optimize by using a fixed-size array for frequencies instead of a hash map.

B. Use a brute force nested loop approach with early breaks to handle reuse.

C. Use a priority queue to track the least recently used character to evict when distinct count exceeds two.

D. Switch to a dynamic programming approach that stores results for substrings with reuse allowed.

Solution

1. Step 1: Understand reuse and input size impact

   Characters can be reused infinitely, but the problem remains longest substring with at most two distinct chars. The input is very long, so efficiency is critical.

2. Step 2: Identify efficient data structure

   Using a fixed-size array for frequencies (size 128 for ASCII) is more efficient than a hash map, reducing overhead and ensuring O(n) time and O(1) space.

3. Step 3: Confirm approach correctness

   The sliding window logic remains the same, but frequency tracking is optimized for speed and memory, suitable for very long inputs with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Fixed-size array frequency tracking is optimal for large inputs with limited charset [OK]

Hint: Fixed-size array beats hash map for fixed charset [OK]

Common Mistakes:

• Using brute force despite input size
• Using complex data structures unnecessarily
• Switching to DP without need