Find All Anagrams in a String

🎯

Find All Anagrams in a String

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

1. Iterate over all substrings of s with length equal to p.
2. For each substring, count the frequency of characters.
3. Compare the frequency map of the substring with that of p.
4. 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.

🧠

Sliding Window with Frequency Map Comparison

💡 This approach improves efficiency by using a sliding window to avoid recounting frequencies from scratch for every substring, reducing redundant work.

Intuition

Maintain a window of length p over s, update character counts as the window slides, and compare frequency maps incrementally.

Algorithm

1. Create frequency map for p.
2. Initialize a sliding window of size p_len over s.
3. For each step, update the window frequency by adding the new character and removing the old one.
4. Compare the window frequency map with p's frequency map; if equal, record the start index.

💡 The challenge is correctly updating counts as the window moves and efficiently comparing maps.

</>

Code

from collections import Counter

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

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

Line Notes

window_count = Counter()Initialize frequency map for current window

window_count[s[i]] += 1Add new character entering the window

if i >= p_lenOnce window size exceeds p_len, remove leftmost character

if window_count[left_char] == 1Remove character from map if count drops to zero

if window_count == p_countCheck if current window is an anagram

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);
        }
        Map<Character, Integer> windowCount = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            if (i >= pLen) {
                char leftChar = s.charAt(i - pLen);
                if (windowCount.get(leftChar) == 1) {
                    windowCount.remove(leftChar);
                } else {
                    windowCount.put(leftChar, windowCount.get(leftChar) - 1);
                }
            }
            if (windowCount.equals(pCount)) {
                res.add(i - pLen + 1);
            }
        }
        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> windowCount = new HashMap<>()Frequency map for sliding window

windowCount.put(c, windowCount.getOrDefault(c, 0) + 1)Add new character to window count

if (i >= pLen)Remove character leaving the window once window size exceeded

windowCount.remove(leftChar)Remove character if count drops to zero

if (windowCount.equals(pCount))Check if current window matches p's frequency

#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]++;
    unordered_map<char, int> windowCount;
    for (int i = 0; i < (int)s.size(); i++) {
        windowCount[s[i]]++;
        if (i >= pLen) {
            char leftChar = s[i - pLen];
            if (windowCount[leftChar] == 1) {
                windowCount.erase(leftChar);
            } else {
                windowCount[leftChar]--;
            }
        }
        if (windowCount == pCount) {
            res.push_back(i - pLen + 1);
        }
    }
    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> windowCount;Frequency map for current sliding window

windowCount[s[i]]++;Add new character entering window

if (i >= pLen)Remove character leaving window after window size reached

windowCount.erase(leftChar);Remove character if count zero to keep map clean

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

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);
    }
    const windowCount = new Map();
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        windowCount.set(c, (windowCount.get(c) || 0) + 1);
        if (i >= pLen) {
            const leftChar = s[i - pLen];
            if (windowCount.get(leftChar) === 1) {
                windowCount.delete(leftChar);
            } else {
                windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            }
        }
        if (mapsEqual(pCount, windowCount)) {
            res.push(i - pLen + 1);
        }
    }
    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 windowCount = new Map();Frequency map for sliding window

windowCount.set(c, (windowCount.get(c) || 0) + 1);Add new character to window count

if (i >= pLen)Remove character leaving window after window size reached

windowCount.delete(leftChar);Remove character if count zero to keep map clean

if (mapsEqual(pCount, windowCount))Check if current window matches p's frequency

⏱

Complexity

TimeO(n * k) where n = len(s), k = number of unique chars in p

SpaceO(k) for frequency maps

Each step updates counts in O(1) and compares maps in O(k), which is much faster than brute force for large n.

💡 If p has 26 unique letters, each step does about 26 comparisons, so for n=100,000 this is about 2.6 million operations, which is feasible.

Interview Verdict: Accepted / Good for medium inputs

This approach is efficient enough for most interview problems and demonstrates understanding of sliding windows and frequency tracking.

🧠

Sliding Window with Two Counters and Match Count Optimization

💡 This approach further optimizes by avoiding full map comparisons at each step, instead tracking how many characters currently match the required frequency.

Intuition

Use two frequency arrays and a match count to track how many characters have the exact needed frequency, sliding the window and updating counts and matches incrementally.

Algorithm

1. Create frequency array for p and initialize a window frequency array.
2. Initialize a match count to track how many characters have matching frequencies.
3. Slide the window over s, updating counts and match count as characters enter and leave.
4. When match count equals number of unique characters in p, record the start index.

💡 The key is carefully updating match count only when frequencies match or mismatch, avoiding costly full map comparisons.

</>

Code

def findAnagrams(s: str, p: str) -> list:
    res = []
    if len(p) > len(s):
        return res
    p_count = [0] * 26
    s_count = [0] * 26
    for c in p:
        p_count[ord(c) - ord('a')] += 1
    for i in range(len(p)):
        s_count[ord(s[i]) - ord('a')] += 1
    matches = 0
    for i in range(26):
        if p_count[i] == s_count[i]:
            matches += 1
    l = 0
    for r in range(len(p), len(s)):
        if matches == 26:
            res.append(l)
        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
    if matches == 26:
        res.append(l)
    return res

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

Line Notes

p_count = [0] * 26Frequency array for p's characters

s_count = [0] * 26Frequency array for current window in s

matches = 0Count of characters whose frequency matches between p and window

if matches == 26All characters match frequency, so window is an anagram

s_count[index_r] += 1Add new character entering window

s_count[index_l] -= 1Remove character leaving window

matches += 1 / matches -= 1Update match count when frequency matches or mismatches

import java.util.*;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length()) return res;
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (char c : p.toCharArray()) pCount[c - 'a']++;
        for (int i = 0; i < p.length(); i++) sCount[s.charAt(i) - 'a']++;
        int matches = 0;
        for (int i = 0; i < 26; i++) {
            if (pCount[i] == sCount[i]) matches++;
        }
        int l = 0;
        for (int r = p.length(); r < s.length(); r++) {
            if (matches == 26) res.add(l);
            int indexR = s.charAt(r) - 'a';
            sCount[indexR]++;
            if (sCount[indexR] == pCount[indexR]) matches++;
            else if (sCount[indexR] == pCount[indexR] + 1) matches--;
            int indexL = s.charAt(l) - 'a';
            sCount[indexL]--;
            if (sCount[indexL] == pCount[indexL]) matches++;
            else if (sCount[indexL] == pCount[indexL] - 1) matches--;
            l++;
        }
        if (matches == 26) res.add(l);
        return res;
    }

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

Line Notes

int[] pCount = new int[26];Frequency array for p

int[] sCount = new int[26];Frequency array for sliding window

int matches = 0;Count of characters matching frequency

if (matches == 26)All characters match, window is an anagram

sCount[indexR]++;Add new character to window count

sCount[indexL]--;Remove character leaving window

matches++; matches--;Update matches when frequency changes

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

using namespace std;

vector<int> findAnagrams(string s, string p) {
    vector<int> res;
    if (p.size() > s.size()) return res;
    vector<int> pCount(26, 0), sCount(26, 0);
    for (char c : p) pCount[c - 'a']++;
    for (int i = 0; i < (int)p.size(); i++) sCount[s[i] - 'a']++;
    int matches = 0;
    for (int i = 0; i < 26; i++) {
        if (pCount[i] == sCount[i]) matches++;
    }
    int l = 0;
    for (int r = (int)p.size(); r < (int)s.size(); r++) {
        if (matches == 26) res.push_back(l);
        int indexR = s[r] - 'a';
        sCount[indexR]++;
        if (sCount[indexR] == pCount[indexR]) matches++;
        else if (sCount[indexR] == pCount[indexR] + 1) matches--;
        int indexL = s[l] - 'a';
        sCount[indexL]--;
        if (sCount[indexL] == pCount[indexL]) matches++;
        else if (sCount[indexL] == pCount[indexL] - 1) matches--;
        l++;
    }
    if (matches == 26) res.push_back(l);
    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

vector<int> pCount(26, 0), sCount(26, 0);Frequency arrays for p and window

int matches = 0;Count of characters matching frequency

if (matches == 26)All characters match, window is an anagram

sCount[indexR]++;Add new character to window count

sCount[indexL]--;Remove character leaving window

matches++; matches--;Update matches when frequency changes

function findAnagrams(s, p) {
    const res = [];
    if (p.length > s.length) return res;
    const pCount = new Array(26).fill(0);
    const sCount = new Array(26).fill(0);
    for (const c of p) pCount[c.charCodeAt(0) - 97]++;
    for (let i = 0; i < p.length; i++) sCount[s.charCodeAt(i) - 97]++;
    let matches = 0;
    for (let i = 0; i < 26; i++) {
        if (pCount[i] === sCount[i]) matches++;
    }
    let l = 0;
    for (let r = p.length; r < s.length; r++) {
        if (matches === 26) res.push(l);
        let indexR = s.charCodeAt(r) - 97;
        sCount[indexR]++;
        if (sCount[indexR] === pCount[indexR]) matches++;
        else if (sCount[indexR] === pCount[indexR] + 1) matches--;
        let indexL = s.charCodeAt(l) - 97;
        sCount[indexL]--;
        if (sCount[indexL] === pCount[indexL]) matches++;
        else if (sCount[indexL] === pCount[indexL] - 1) matches--;
        l++;
    }
    if (matches === 26) res.push(l);
    return res;
}

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

Line Notes

const pCount = new Array(26).fill(0);Frequency array for p

const sCount = new Array(26).fill(0);Frequency array for sliding window

let matches = 0;Count of characters matching frequency

if (matches === 26)All characters match, window is an anagram

sCount[indexR]++;Add new character to window count

sCount[indexL]--;Remove character leaving window

matches++; matches--;Update matches when frequency changes

⏱

Complexity

TimeO(n) where n = len(s)

SpaceO(1) since frequency arrays are fixed size 26

Each character is processed once, and match count updates are O(1), making this the most efficient approach.

💡 For n=100,000, this approach does about 100,000 operations, which is very fast and scalable.

Interview Verdict: Accepted / Optimal

This is the best approach to implement in interviews for this problem, showing mastery of sliding window and frequency tracking.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the optimal sliding window with match count approach is best. Brute force is only for explanation, and the basic sliding window is a good intermediate step.

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

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to optimized sliding window solutions, and finally discuss edge cases and test thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the sliding window technique with frequency maps.Step 4: Optimize further by tracking matches to avoid full map comparisons.Step 5: Code the optimal solution and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify the right data structures (frequency maps), use sliding windows effectively, optimize comparisons, and handle edge cases correctly.

Common Follow-ups

• What if the input contains Unicode characters? → Use hash maps instead of fixed arrays.
• Can you find the first anagram instead of all? → Stop when first match found.

💡 These follow-ups test your adaptability to variations and understanding of data structures beyond ASCII.

🔍

Pattern Recognition

When to Use

1) Asked to find substrings matching a pattern's character composition, 2) Need to find all occurrences, 3) Order of characters doesn't matter, 4) Efficient substring checking required.

Signature Phrases

'find all start indices of p's anagrams in s''rearranging the letters'

NOT This Pattern When

Substring search problems where order matters or exact substring matching is required (e.g., KMP algorithm problems).

Similar Problems

Minimum Window Substring - similar frequency tracking but with minimum length windowPermutation in String - check if any permutation of p is substring of sGroup Anagrams - group strings by character frequency signature

Practice

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

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace prefix_sum and seen dictionary for each index

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}; Index 1: num=1 -> prefix_sum=0, max_length=1-(-1)=2; Index 2: num=0 -> prefix_sum=-1, max_length=max(2,2-0)=2.

2. Step 2: Return max_length after full iteration

   max_length is 2, corresponding to subarray [0,1] or [1,0].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums correctly track balance; max_length updated only when prefix_sum repeats [OK]

Hint: Track prefix sums and earliest indices carefully [OK]

Common Mistakes:

• Off-by-one in max_length calculation
• Not initializing seen with 0:-1
• Updating max_length incorrectly

2. Given the following code and input nums = [3,1,1,1,5], x = 5, what is the returned value?

easy

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate totalSum and target

   totalSum = 3+1+1+1+5 = 11; target = 11 - 5 = 6.

2. Step 2: Use sliding window to find longest subarray summing to 6

   Window expands: [3] sum=3, [3,1] sum=4, [3,1,1] sum=5, [3,1,1,1] sum=6 -> max_len=4; next, add 5 sum=11 > 6, shrink from left: remove 3 sum=8 >6, remove 1 sum=7 >6, remove 1 sum=6 -> max_len=4 remains (subarray [1,1,1]).

3. Step 3: Calculate minimum operations

   Minimum removals = array length - max_len = 5 - 4 = 1.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Longest subarray length 4 -> min ops = 1 [OK]

Hint: Sliding window finds longest subarray sum [OK]

Common Mistakes:

• Off-by-one errors in window length calculation
• Miscomputing sums when shrinking window
• Confusing min operations with longest subarray length

3. Identify the bug in the following code snippet for longest arithmetic subsequence length:

medium

A. Line assigning dp[i][diff] without adding 1 to prev_len

B. Line initializing max_len to 0 instead of 1

C. Line creating dp as list of dicts instead of list of lists

D. Line returning max_len if max_len > 0 else n

Solution

1. Step 1: Examine dp update line

   dp[i][diff] should be prev_len + 1 to extend the subsequence; missing +1 means subsequence length never grows.

2. Step 2: Check other lines

   max_len initialization and return line are correct; dp as list of dicts is intentional for difference tracking.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing +1 causes incorrect subsequence length calculation [OK]

Hint: dp[i][diff] must increment prev_len by 1 to extend subsequence [OK]

Common Mistakes:

• Forgetting to add 1 when updating dp[i][diff]
• Initializing max_len incorrectly
• Confusing subsequence with subarray

4. What is the time complexity of the optimal approach that counts subarrays with maximum bounded by left and right using the subtraction of two counts (countAtMost)?

medium

A. O(n) because it makes two linear passes over the array

B. O(n^2) because it checks all subarrays explicitly

C. O(n log n) due to sorting the array before counting

D. O(n) with O(n) extra space to store intermediate counts

Solution

1. Step 1: Identify operations in countAtMost

   countAtMost iterates over the array once, updating counters in O(1) time per element.

2. Step 2: Analyze overall complexity

   numSubarrayBoundedMax calls countAtMost twice, each O(n), so total time is O(n). No sorting or nested loops involved.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans -> O(n) time, constant space [OK]

Hint: Two linear scans, no nested loops or sorting [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking extra space is O(n)

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