Find All Anagrams in a String LeetCode 438

Pattern Recognition in Find All Anagrams in a String (LeetCode 438)

Step 1: Identify the Core Pattern

This problem falls under the sliding window and frequency counting pattern. Key insight: all anagrams of p have the same character counts. By maintaining a constant-size window in s, we can check for matches in O(1) time per step.

Step 2: Fixed-Size Sliding Window Pattern

• Window length = p.length.
• Incrementally update counts as window slides.
• Compare counts at each step.

Step 3: Frequency Counting Pattern

• Use array of size 26 for lowercase letters.
• Increment count for new char entering window.
• Decrement count for char leaving window.
• Efficient comparison: toString() or loop over 26 elements.

Step 4: Dry Run Example

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

Step 5: Recruiter-Friendly Pattern Tips

Step 6: Variations & Related Patterns

• Unicode Support: Switch from array to hashmap, O(n) still.
• Variable Window: LC76 Minimum Window Substring, requires dynamic window resizing.
• Count Only: Return number of anagrams instead of indices.
• Related Problems: LC567 Permutation in String, LC49 Group Anagrams, LC242 Valid Anagram.

Step 7: Summary of Recruiter Insights

• Highlight **pattern recognition** in interviews: "I identified this as sliding window + frequency counting."
• Explain **optimization reasoning**: "From O(n·m log m) brute force to O(n) sliding window."
• Discuss **edge case handling** explicitly: duplicates, empty strings, overlapping windows.
• Show **dry run** for clarity to the interviewer.
• Mention **related patterns** or problems for breadth: variable window, Unicode support.

By following this structured, recruiter-oriented approach, you convey deep **problem understanding, pattern insight, and systematic solution strategy**, which aligns naturally with your other content files.

Interview Focused for Find All Anagrams in a String LeetCode 438

Interview Framing

“A naive way is to sort every substring of length p and compare to sorted p, but that's O(n·m log m). Optimally, use a fixed-size sliding window: track frequency counts for p and current window. Slide the window, update counts in O(1), and when they match, add the start index. This is O(n) time. Example: s = "cbaebabacd", p = "abc" → indices [0,6].”

How to Explain to Interviewers

“Start with brute force: for each start i, take s[i:i+m], sort and compare to sorted p. Then optimize to sliding window: precompute p's freq array. Initialize window freq for first m chars. For each step, add right char, remove left, compare freqs. If equal, record i. Use array[26] for lowercase efficiency.”

One-Go Interview Answer

“For Find All Anagrams in a String, brute force checks each substring by sorting or hashing, O(n·m log m) or O(n·m). The optimal uses a fixed sliding window of size p.length with two freq arrays (26 for lowercase). Slide: increment right, decrement left, compare arrays in O(26). Collect starts when match. O(n) time, O(1) space. Return [] if none.”

In FAANG, stress: Constant-time freq compare via arrays or counters. Variations: Uppercase? Unicode? (Switch to hashmap). Related: If variable size, like LC76 Minimum Window Substring.

FAANG Interview Strategy for LeetCode 438: Find All Anagrams in a String

Mastering LeetCode 438 for FAANG requires structured thinking: restate, brute force, optimize, analyze, and dry run. Emphasize pattern recognition in sliding window and frequency counting problems.

Stepwise Interview Script

1. Restate Problem:

   Clarify inputs and outputs: "Find start indices of all anagrams of p in s. Anagram = same characters and counts. Example: s='cbaebabacd', p='abc' → [0,6]. Lowercase only?"

   Recruiter Insight: Shows comprehension, asks clarifying constraints.

2. Brute Force:

   Check all substrings: sort each s[i:i+m] and compare to sorted p. Time O(n·m log m).

   Recruiter Insight: Always show brute force first, even if inefficient — demonstrates problem-solving approach.

3. Optimized Sliding Window:

   Use fixed-size window of length m = p.length with two frequency arrays of size 26.

   • Initialize pFreq and windowFreq for first m chars
   • Slide window: +s[r], -s[l], l++
   • If windowFreq == pFreq, add l to result

   Step	Window	WindowFreq	Match?
   Init	cba	[1,1,1,...]	Yes → add 0
   Slide 1	bae	[1,1,0,1,...]	No
   Slide 6	bac	[1,1,1,...]	Yes → add 6

   Recruiter Insight: Emphasize incremental updates and O(1) comparisons; shows mastery of sliding window and frequency counting.

4. Complexity Analysis:
   • Time: O(n), single pass, each char O(1), compare arrays O(26)
   • Space: O(26), constant; or O(m) if using hashmap for unicode

   Recruiter Insight: Always articulate time-space trade-offs and justify array vs hashmap choice.

5. Dry Run Example:

   s = "cbaebabacd", p = "abc"
   pFreq = [1,1,1,...] (a,b,c)
   Window "cba": match → add 0
   Slide → "bae": no match
   Continue → "bac" at 6: match → add 6
   Return [0,6]

   Recruiter Insight: Stepwise dry runs show clarity of thought and help spot edge cases early.

Common Mistakes & Pitfalls

Questions to Ask Interviewer

• Alphabet? Lowercase only? (Yes, per constraints)
• Order of indices? (Any order)
• Max lengths? (O(n) validated)
• Empty p/s allowed? (Return all indices 0 to n-1 if empty, else constraints min 1)

Follow-Up Variations

• Unicode / uppercase letters? (Use hashmap instead of fixed array)
• Count total anagrams instead of indices
• K mismatches allowed? (Track tolerance in freq arrays)

Solution Approach — Find All Anagrams in a String (LeetCode 438)

The optimal solution uses a fixed-size sliding window over s with window length m = p.length. Two frequency representations are maintained: one for the target string p and one for the current window in s. The window is initialized on the first m characters and then moved right by one position repeatedly; updates are incremental (add the new right character, remove the old left character). For the lowercase-English constraint, fixed-size arrays of length 26 give the best practical performance.

High-level steps

1. If m > n (where n = s.length), immediately return an empty array.
2. Build frequency array pCount[26] for p.
3. Initialize windowCount[26] with the first m characters of s (if any).
4. Compare counts for equality; if equal, record index 0.
5. For each right index i from m to n-1:
   • Increment count for s[i] (new right).
   • Decrement count for s[i - m] (removed left).
   • If counts match, record start index i - m + 1.
6. Return collected indices.

Pseudocode (whiteboard-friendly)

FUNCTION findAnagrams(s, p):
  n ← length(s)
  m ← length(p)
  IF m > n:
    RETURN []

  pCount ← new int[26] // all zeros
  wCount ← new int[26] // all zeros

  FOR i FROM 0 TO m-1:
    pCount[ ord(p[i]) - ord('a') ] += 1
    wCount[ ord(s[i]) - ord('a') ] += 1

  results ← []
  IF pCount == wCount:
    results.append(0)

  FOR i FROM m TO n-1:
    wCount[ ord(s[i]) - ord('a') ] += 1
    wCount[ ord(s[i-m]) - ord('a') ] -= 1
    IF pCount == wCount:
      results.append(i - m + 1)

  RETURN results
  

Micro-optimization: tracking matches (avoid full-array equality)

Rather than comparing two arrays element-by-element on every slide, maintain a matches counter equal to the number of character positions (0..25) for which pCount[c] === wCount[c]. Update matches only for characters that changed during a slide. When matches === 26, the window is an anagram. This reduces per-step work to a few integer comparisons and increments/decrements, and it is often faster in practice because it avoids scanning all 26 entries every time.

Why the matches trick is correct (intuition)

The invariant is: matches equals the count of indices c in [0..25] where pCount[c] == wCount[c]. When a single character's count changes, only that character's equality relation can change, so updating matches locally preserves the invariant. Equality of full arrays is equivalent to matches === 26.

Optimized JavaScript implementation (practical)

// Returns array of start indices where p's anagrams begin in s
function findAnagrams(s, p) {
  const n = s.length, m = p.length;
  if (m > n) return [];

  const pCount = new Array(26).fill(0);
  const wCount = new Array(26).fill(0);

  for (let i = 0; i < m; i++) {
    pCount[p.charCodeAt(i) - 97]++;
    wCount[s.charCodeAt(i) - 97]++;
  }

  let matches = 0;
  for (let i = 0; i < 26; i++) if (pCount[i] === wCount[i]) matches++;

  const res = [];
  if (matches === 26) res.push(0);

  for (let i = m; i < n; i++) {
    const r = s.charCodeAt(i) - 97;        // new right char
    const l = s.charCodeAt(i - m) - 97;    // removed left char

    // update right char
    if (wCount[r] === pCount[r]) matches--;
    wCount[r]++;
    if (wCount[r] === pCount[r]) matches++;

    // update left char
    if (wCount[l] === pCount[l]) matches--;
    wCount[l]--;
    if (wCount[l] === pCount[l]) matches++;

    if (matches === 26) res.push(i - m + 1);
  }

  return res;
}

Proof sketch of correctness

Initialization sets the window counts to the first m characters and builds the target frequency. The loop invariant after each iteration is: windowCount represents counts of the current window, and matches (if used) accurately reflects equality positions between arrays. Sliding updates maintain the correct counts by incrementing the new right character and decrementing the removed left character. Since every possible window of length m is considered exactly once, and the detection condition is exact frequency equality, the algorithm returns all valid starting indices.

Complexity analysis (practical considerations)

Time complexity is O(n) where each character of s is processed a constant number of times. For fixed alphabets the per-step work is O(1) (26 is a constant). Space complexity is O(1) for fixed-size arrays or O(u) if a hashmap is used (where u is the number of distinct characters).

• Best case: O(n) — normal execution.
• Worst case: O(n) — identical asymptotic bound; matches trick reduces constant factors.

Implementation notes & pitfalls

• Character indexing: For ASCII lowercase, use charCodeAt(i) - 97. Validate character set assumptions when constraints change.
• Off-by-one errors: When pushing a match during sliding, the starting index is i - m + 1 (where i is the right pointer). Initial window corresponds to index 0.
• Equality checks: Avoid naive object/array equality in languages where it compares references. Use language-appropriate utilities (e.g., Arrays.equals in Java, SequenceEqual in C#), or maintain a matches counter to detect full equality in O(1).
• Unicode / large alphabets: If characters are not limited to 26 lowercase letters, switch to a hashmap keyed by character. The algorithm remains linear, but the constant factor and memory usage increase.
• Streaming s: For very large s (or streamed input), use a fixed-size queue or circular buffer to manage the window and update counts as bytes arrive. Maintain the same logic to emit indices (or counts) online.

Testing guidance

Include tests that validate correctness and edge behavior:

• Basic examples from the problem statement.
• All duplicates: s = "aaaa", p = "aa" → overlapping matches.
• p longer than s: s = "a", p = "aa" → [].
• Unicode test (if implementing hashmap variant).
• Randomized stress tests comparing optimized vs brute-force (for small sizes) to assert equivalence.

When the approach changes

The array-based sliding-window is the preferred approach when the alphabet is small and fixed. When confronted with arbitrary or very large alphabets, or when memory is constrained, adapt the representation to hashmaps, and document the tradeoffs during an interview.

Deep Dive into LeetCode 438 Find All Anagrams in a String

Exploring the problem's nuances builds intuition for sliding window and frequency counting patterns.

Problem Breakdown

• Inputs: s (len n), p (len m), lowercase letters (n,m ≤ 3e4).
• Output: Array of start indices of anagrams, any order.
• Core: Find fixed-length substrings with exact char frequencies as p.

Intuition

Anagrams have identical sorted forms or freq maps. Brute sorts each window; optimize by sliding, updating freq incrementally—add right, remove left—for O(1) checks.

Dry Run: s="cbaebabacd", p="abc"

• pCount: a:1, b:1, c:1
• Window[0:2] "cba": a:1,b:1,c:1 → match, add 0
• Slide to [1:3] "bae": -c +e → a:1,b:1,e:1 → no
• Continue... [6:8] "bac": b:1,a:1,c:1 → match, add 6

Variations & Discussions

• Unicode: Use Map, O(n) time still, space O(unique chars).
• Min anagram window: Variable window like LC76.
• Count instead of indices: Increment counter on match.
• Performance: Arrays 2x faster than maps in practice.

Time and Space Complexity

Time: O(n), single pass, O(1) per step (26 comparisons).
Space: O(1), fixed arrays. Hashmap: O(m) worst.

Common Pitfalls in Find All Anagrams in a String LeetCode 438

Top Pitfalls & Fixes

Stepwise Corrected JS Implementation

Incremental updates with recruiter-friendly reasoning:

// Optimized with proper initialization & comparison
function findAnagrams(s, p) {
  const n = s.length, m = p.length;
  if (m > n) return []; // Pitfall: early return

  const pCount = new Array(26).fill(0);
  const wCount = new Array(26).fill(0);

  // Initialize frequency counts
  for (let i = 0; i < m; i++) {
    pCount[p.charCodeAt(i) - 97]++;
    wCount[s.charCodeAt(i) - 97]++;
  }

  const res = [];
  if (pCount.toString() === wCount.toString()) res.push(0);

  // Slide window
  for (let i = m; i < n; i++) {
    wCount[s.charCodeAt(i) - 97]++;       // Add new char
    wCount[s.charCodeAt(i - m) - 97]--;   // Remove old char
    if (pCount.toString() === wCount.toString()) res.push(i - m + 1);
  }

  return res;
}

Recruiter Insights

• Emphasize **understanding pitfalls** in interviews: shows attention to detail.
• Explain **why early return is crucial**: O(n) guarantee and avoids errors.
• Highlight **array vs set/map decisions**: shows optimization awareness.
• Dry run code during interview to prove correctness on edge cases.
• Discuss handling duplicates, overlapping windows, and empty input explicitly.

Edge Cases and Real-World Applications for LeetCode 438

Key Edge Cases

Real-World Applications

• Text Processing: Detect permutations in documents, logs, or searches.
• Bioinformatics: DNA/RNA sequence pattern matching and motif finding.
• Plagiarism Detection: Identify rearranged or paraphrased phrases.
• Data Deduplication: Group entries that are anagrams to avoid redundancy.
• Search Engines: Suggest anagram queries or alternative spellings.

Recruiter Insights

• Discussing **edge cases explicitly** shows you think beyond happy-paths.
• Dry-run these edge cases during interviews to illustrate correctness.
• Relate **real-world scenarios**: demonstrates applied problem-solving thinking.
• Explain how your **optimized sliding window** handles each edge elegantly.

Time and Space Complexity for Find All Anagrams in a String LeetCode 438

Optimized sliding window achieves efficiency for large inputs.

Time Complexity

O(n): Initialize O(m), slide O(n-m) steps, each O(1) update + O(26) compare. Effective O(n) since 26 constant.

Space Complexity

O(1): Fixed arrays[26]. Hashmap variant O(m) for unique chars in p.

Comparisons

Bottlenecks: Frequent comparisons; optimize with array equality or counter diff tracking.

Related Problems to Find All Anagrams in a String LeetCode 438

Build skills with similar sliding window and frequency counting problems.

• LC567 Permutation in String: Check if any anagram exists (bool, not all indices).
• LC76 Minimum Window Substring: Variable window for min substring covering chars (not exact freq).
• LC3 Longest Substring Without Repeating: Variable window, unique chars (freq <=1).
• LC49 Group Anagrams: Sort/hash to group list of strings by anagrams.
• LC242 Valid Anagram: Basic freq compare for two strings.
• LC30 Substring with Concatenation: Fixed window for word concatenations.

Practice these for mastery in LeetCode 438 Solution patterns.

FAQs for Find All Anagrams in a String LeetCode 438

Recruiter Insights

• Answer concisely, then **walk through dry run** and edge cases.
• Emphasize **pattern recognition** and **optimization choices**.
• Mention **related problems** to demonstrate breadth of knowledge.
• Highlight **robustness**: duplicates, overlaps, empty inputs, and Unicode considerations.