What happens if you not handling edge cases where p is longer than s?

Index errors or incorrect results Fix: Return empty list immediately if p length > s length

Interview Prepknowing-what-to-trackmediumAmazonFacebookGoogle

Find All Anagrams in a String

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumHASH_MAPAmazonFacebookGoogle

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.

💡 This problem is about finding all substrings that are anagrams of a given pattern. Beginners often struggle because they try to check every substring naively, which is inefficient. Understanding how to track character frequencies and use sliding windows is key.

📋

Problem Statement

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

💡

Example

Input"s = \"cbaebabacd\", p = \"abc\""

Output[0, 6]

The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".

Input"s = \"abab\", p = \"ab\""

Output[0, 1, 2]

The substrings are "ab", "ba", and "ab" starting at indices 0, 1, and 2 respectively.

p longer than s → empty output
s and p are identical → output [0]
s or p is a single character → output all indices where characters match
s contains repeated characters but p has unique characters → only exact matches

⚠️

Common Mistakes

Comparing frequency maps by converting to strings or sorting every time

Leads to high time complexity and TLE

✅ Use sliding window with incremental updates and match count optimization

Not removing characters from frequency map when count drops to zero

Frequency maps differ even when substrings are anagrams, causing false negatives

✅ Remove character keys when their count reaches zero

Not handling edge cases where p is longer than s

Index errors or incorrect results

✅ Return empty list immediately if p length > s length

Off-by-one errors in sliding window boundaries

Missed or extra indices in output

✅ Carefully track window start and end indices, especially when adding/removing characters

Using mutable default arguments or global variables in recursive or iterative code

Unexpected behavior or bugs

✅ Use local variables and initialize fresh frequency maps per function call

🧠

Brute Force (Check All Substrings)

💡 This approach exists to build intuition by directly checking every possible substring of length p and verifying if it is an anagram. It is simple but inefficient, highlighting why optimization is needed.

Intuition

Check every substring of s with length equal to p, and for each substring, check if it contains the same characters with the same frequency as p.

Algorithm

Iterate over all substrings of s with length equal to p.
For each substring, count the frequency of characters.
Compare the frequency map of the substring with that of p.
If they match, record the start index.

💡 The main difficulty is realizing that checking every substring independently leads to repeated work and inefficiency.

</>

Code

from collections import Counter

def findAnagrams(s: str, p: str) -> list:
    res = []
    p_len = len(p)
    p_count = Counter(p)
    for i in range(len(s) - p_len + 1):
        window = s[i:i+p_len]
        window_count = Counter(window)
        if window_count == p_count:
            res.append(i)
    return res

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

Line Notes

from collections import CounterImport Counter to easily count character frequencies

p_count = Counter(p)Precompute frequency of characters in p once

for i in range(len(s) - p_len + 1)Iterate over all possible substrings of length p_len

window_count = Counter(window)Count characters in current substring from scratch

if window_count == p_countCheck if current substring is an anagram by comparing counts

res.append(i)Record starting index if an anagram is found

import java.util.*;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int pLen = p.length();
        Map<Character, Integer> pCount = new HashMap<>();
        for (char c : p.toCharArray()) {
            pCount.put(c, pCount.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i <= s.length() - pLen; i++) {
            String window = s.substring(i, i + pLen);
            Map<Character, Integer> windowCount = new HashMap<>();
            for (char c : window.toCharArray()) {
                windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            }
            if (windowCount.equals(pCount)) {
                res.add(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findAnagrams("cbaebabacd", "abc")); // Output: [0, 6]
    }
}

Line Notes

Map<Character, Integer> pCount = new HashMap<>()Create frequency map for p

for (int i = 0; i <= s.length() - pLen; i++)Loop over all substrings of length pLen

Map<Character, Integer> windowCount = new HashMap<>()Create frequency map for current substring

if (windowCount.equals(pCount))Check if current substring is an anagram

res.add(i)Add starting index to result list

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

vector<int> findAnagrams(string s, string p) {
    vector<int> res;
    int pLen = p.size();
    unordered_map<char, int> pCount;
    for (char c : p) {
        pCount[c]++;
    }
    for (int i = 0; i <= (int)s.size() - pLen; i++) {
        unordered_map<char, int> windowCount;
        for (int j = i; j < i + pLen; j++) {
            windowCount[s[j]]++;
        }
        if (windowCount == pCount) {
            res.push_back(i);
        }
    }
    return res;
}

int main() {
    vector<int> result = findAnagrams("cbaebabacd", "abc");
    for (int idx : result) cout << idx << " ";
    cout << endl; // Output: 0 6
    return 0;
}

Line Notes

unordered_map<char, int> pCount;Frequency map for p

for (int i = 0; i <= (int)s.size() - pLen; i++)Iterate over all substrings of length pLen

unordered_map<char, int> windowCount;Frequency map for current substring

if (windowCount == pCount)Compare frequency maps to check anagram

res.push_back(i);Store starting index if anagram found

function findAnagrams(s, p) {
    const res = [];
    const pLen = p.length;
    const pCount = new Map();
    for (const c of p) {
        pCount.set(c, (pCount.get(c) || 0) + 1);
    }
    for (let i = 0; i <= s.length - pLen; i++) {
        const window = s.substring(i, i + pLen);
        const windowCount = new Map();
        for (const c of window) {
            windowCount.set(c, (windowCount.get(c) || 0) + 1);
        }
        if (mapsEqual(pCount, windowCount)) {
            res.push(i);
        }
    }
    return res;
}

function mapsEqual(m1, m2) {
    if (m1.size !== m2.size) return false;
    for (const [key, val] of m1) {
        if (m2.get(key) !== val) return false;
    }
    return true;
}

// Example usage
console.log(findAnagrams("cbaebabacd", "abc")); // Output: [0, 6]

Line Notes

const pCount = new Map();Create frequency map for p

for (let i = 0; i <= s.length - pLen; i++)Loop over all substrings of length pLen

const windowCount = new Map();Frequency map for current substring

if (mapsEqual(pCount, windowCount))Check if current substring is an anagram

res.push(i);Add starting index to result array

⏱

Complexity

TimeO((n - m + 1) * m) where n = len(s), m = len(p)

SpaceO(m) for frequency maps

For each of the n-m+1 substrings, we count frequencies in O(m) time, leading to O(n*m) total.

💡 If s and p are length 20, this means about 400 operations, but for 100,000 length strings this becomes 10 billion operations, which is too slow.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is useful to understand the problem and motivate optimizations.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n*m)`	`O(m)`	No	N/A	Mention only - never code
2. Sliding Window with Frequency Map Comparison	`O(n*k) where k = unique chars in p`	`O(k)`	No	N/A	Good intermediate solution
3. Sliding Window with Match Count Optimization	`O(n)`	`O(1)`	No	N/A	Code this for best performance

Practice

(1/5)

1. The following code attempts to solve the fruits problem using a sliding window. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def totalFruit(fruits):
    basket = {}
    left = 0
    max_length = 0
    for right in range(len(fruits)):
        basket[fruits[right]] = basket.get(fruits[right], 0) + 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            # BUG: Missing removal of fruit type when count reaches zero
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

medium

A. Line where basket[fruits[right]] is incremented

B. Line where basket[fruits[left]] is decremented

C. Line where fruit type is deleted when count reaches zero (missing here)

D. Line where max_length is updated

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Identify missing removal of fruit type

Step 2: Consequence of missing deletion

Final Answer:

Quick Check:

Solution

Step 1: Identify outer loop complexity

Step 2: Analyze operations inside loop

Final Answer:

Quick Check:

Solution

Step 1: Understand window size meaning

Step 2: Identify impact of wrong window size

Final Answer:

Quick Check:

Solution

Step 1: Identify odd number condition with negatives

Step 2: Modify odd check

Final Answer:

Quick Check:

Solution

Step 1: Understand problem change

Step 2: Modify sliding window logic

Final Answer:

Quick Check:

Ready to prove it?