39. Find All Anagrams in a String

🔗 LeetCode Problem: 438. Find All Anagrams in a String
📊 Difficulty: Medium
🏷️ Topics: Hash Table, String, Sliding Window

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, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
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".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints: - 1 <= s.length, p.length <= 3 * 10^4 - s and p consist of lowercase English letters.

---

🎨 Visual Understanding

The Problem Visualized

s = "cbaebabacd", p = "abc"

Find all substrings of length 3 that are anagrams of "abc":

Position 0: "cba" → c:1, b:1, a:1 = abc ✓
Position 1: "bae" → b:1, a:1, e:1 ≠ abc ✗
Position 2: "aeb" → a:1, e:1, b:1 ≠ abc ✗
Position 3: "eba" → e:1, b:1, a:1 ≠ abc ✗
Position 4: "bab" → b:2, a:1 ≠ abc ✗
Position 5: "aba" → a:2, b:1 ≠ abc ✗
Position 6: "bac" → b:1, a:1, c:1 = abc ✓
Position 7: "acd" → a:1, c:1, d:1 ≠ abc ✗

Answer: [0, 6]

Key Observation: Fixed Window Size

Window size = p.length (fixed)
Need to check if window is anagram of p

Anagram check:
Two strings are anagrams if they have:
- Same character frequencies
- Same length (already guaranteed by fixed window)

Example:
p = "abc" → {a:1, b:1, c:1}
window = "cba" → {c:1, b:1, a:1}
Same frequencies ✓ Anagram!

Visual Process

s = "cbaebabacd", p = "abc"
p frequency: {a:1, b:1, c:1}

Window slides through s:

[c b a] e b a b a c d → {c:1, b:1, a:1} = p ✓ Index 0
c [b a e] b a b a c d → {b:1, a:1, e:1} ≠ p ✗
c b [a e b] a b a c d → {a:1, e:1, b:1} ≠ p ✗
c b a [e b a] b a c d → {e:1, b:1, a:1} ≠ p ✗
c b a e [b a b] a c d → {b:2, a:1} ≠ p ✗
c b a e b [a b a] c d → {a:2, b:1} ≠ p ✗
c b a e b a [b a c] d → {b:1, a:1, c:1} = p ✓ Index 6
c b a e b a b [a c d] → {a:1, c:1, d:1} ≠ p ✗

Result: [0, 6]

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

For each position in s:
1. Extract substring of length p.length
2. Check if it's an anagram of p
3. If yes, add index to result

Why This Works: - Checks all windows - Guaranteed to find all anagrams - Easy to understand

Why This Fails Requirements: - Time complexity O(n × m) where n = s.length, m = p.length - Recounts frequencies for each window - Too slow for large strings - Not optimal for interviews

Implementation

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();

    if (s.length() < p.length()) {
        return result;
    }

    // Get frequency map of p
    Map<Character, Integer> pMap = new HashMap<>();
    for (char c : p.toCharArray()) {
        pMap.put(c, pMap.getOrDefault(c, 0) + 1);
    }

    // Check each window
    for (int i = 0; i <= s.length() - p.length(); i++) {
        String window = s.substring(i, i + p.length());

        if (isAnagram(window, pMap)) {
            result.add(i);
        }
    }

    return result;
}

private boolean isAnagram(String window, Map<Character, Integer> pMap) {
    Map<Character, Integer> windowMap = new HashMap<>();
    for (char c : window.toCharArray()) {
        windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
    }
    return windowMap.equals(pMap);
}

⏰ Time: O(n × m) - n windows, each checked in O(m)
💾 Space: O(m) - for frequency maps

---

✅ Approach 2: Sliding Window with Frequency Array (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use fixed-size sliding window with frequency array:

1. Build frequency array for p
2. Use sliding window of size p.length
3. For each window, compare frequencies
4. If match, add starting index

Key optimization: 
Instead of rebuilding frequency map each time,
maintain running frequency as window slides

Visual Explanation:

s = "cbaebabacd", p = "abc"

p frequency: [a:1, b:1, c:1, ...]

Initial window [c b a]:
window frequency: [a:1, b:1, c:1, ...]
Match! Add index 0

Slide: Remove 'c', Add 'e'
window [b a e]:
window frequency: [a:1, b:1, e:1, ...]
No match (has 'e', missing 'c')

Continue sliding...

Why This Works:

Fixed window sliding:
1. Calculate frequency for first window
2. Slide window: remove left char, add right char
3. Compare frequencies in O(26) = O(1) time
4. Total: O(n) time

Frequency matching:
- Use array of size 26 for lowercase letters
- Compare arrays element by element
- Or use counter variable for efficiency

Implementation (Approach 1: Array Comparison)

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();

    if (s.length() < p.length()) {
        return result;
    }

    // Build frequency array for p
    int[] pCount = new int[26];
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }

    // Build frequency array for first window
    int[] sCount = new int[26];
    for (int i = 0; i < p.length(); i++) {
        sCount[s.charAt(i) - 'a']++;
    }

    // Check first window
    if (Arrays.equals(pCount, sCount)) {
        result.add(0);
    }

    // Slide window through s
    for (int i = p.length(); i < s.length(); i++) {
        // Add new character (right of window)
        sCount[s.charAt(i) - 'a']++;

        // Remove old character (left of window)
        sCount[s.charAt(i - p.length()) - 'a']--;

        // Check if current window is anagram
        if (Arrays.equals(pCount, sCount)) {
            result.add(i - p.length() + 1);
        }
    }

    return result;
}

⏰ Time: O(n × 26) = O(n) - n windows, each compared in O(26)
💾 Space: O(1) - arrays of fixed size 26

---

✅ Approach 3: Sliding Window with Counter (Most Optimal)

The Further Optimization 💡

Core Logic:

Instead of comparing arrays each time,
use a counter to track matches:

matches = number of characters with matching frequency
If matches == 26, we have an anagram

Update counter as window slides:
- When frequency matches target: matches++
- When frequency stops matching: matches--

Implementation (Approach 2: With Counter)

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();

    if (s.length() < p.length()) {
        return result;
    }

    // Build frequency arrays
    int[] pCount = new int[26];
    int[] sCount = new int[26];

    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }

    // Initialize first window and count matches
    int matches = 0;
    for (int i = 0; i < p.length(); i++) {
        sCount[s.charAt(i) - 'a']++;
    }

    // Count initial matches
    for (int i = 0; i < 26; i++) {
        if (pCount[i] == sCount[i]) {
            matches++;
        }
    }

    // Check first window
    if (matches == 26) {
        result.add(0);
    }

    // Slide window
    for (int i = p.length(); i < s.length(); i++) {
        // Add right character
        int rightIdx = s.charAt(i) - 'a';
        sCount[rightIdx]++;
        if (sCount[rightIdx] == pCount[rightIdx]) {
            matches++;
        } else if (sCount[rightIdx] == pCount[rightIdx] + 1) {
            matches--;
        }

        // Remove left character
        int leftIdx = s.charAt(i - p.length()) - 'a';
        sCount[leftIdx]--;
        if (sCount[leftIdx] == pCount[leftIdx]) {
            matches++;
        } else if (sCount[leftIdx] == pCount[leftIdx] - 1) {
            matches--;
        }

        // Check if anagram
        if (matches == 26) {
            result.add(i - p.length() + 1);
        }
    }

    return result;
}

⏰ Time: O(n) - single pass, O(1) comparison per window
💾 Space: O(1) - arrays of fixed size 26

---

🔍 Step-by-Step Execution

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

Initial State:
═══════════════════════════════════════════════════════════════════
s = "cbaebabacd"
p = "abc"

pCount = [a:1, b:1, c:1, rest:0]
sCount = [all 0]


Step 1: Build first window [c b a]
═══════════════════════════════════════════════════════════════════
Add s[0]='c': sCount[c]=1
Add s[1]='b': sCount[b]=1
Add s[2]='a': sCount[a]=1

sCount = [a:1, b:1, c:1, rest:0]

Compare: pCount == sCount? YES ✓
Add index 0 to result

result = [0]


Step 2: Slide window to position 1 [b a e]
═══════════════════════════════════════════════════════════════════
Remove s[0]='c': sCount[c]=0
Add s[3]='e': sCount[e]=1

sCount = [a:1, b:1, c:0, e:1, rest:0]

Compare: pCount == sCount? NO ✗
(pCount has c:1, sCount has c:0)


Step 3: Slide window to position 2 [a e b]
═══════════════════════════════════════════════════════════════════
Remove s[1]='b': sCount[b]=0
Add s[4]='b': sCount[b]=1

sCount = [a:1, b:1, c:0, e:1, rest:0]

Compare: pCount == sCount? NO ✗


Step 4: Slide window to position 3 [e b a]
═══════════════════════════════════════════════════════════════════
Remove s[2]='a': sCount[a]=0
Add s[5]='a': sCount[a]=1

sCount = [a:1, b:1, c:0, e:1, rest:0]

Compare: pCount == sCount? NO ✗


Step 5: Slide window to position 4 [b a b]
═══════════════════════════════════════════════════════════════════
Remove s[3]='e': sCount[e]=0
Add s[6]='b': sCount[b]=2

sCount = [a:1, b:2, c:0, rest:0]

Compare: pCount == sCount? NO ✗
(pCount has b:1, sCount has b:2)


Step 6: Slide window to position 5 [a b a]
═══════════════════════════════════════════════════════════════════
Remove s[4]='b': sCount[b]=1
Add s[7]='a': sCount[a]=2

sCount = [a:2, b:1, c:0, rest:0]

Compare: pCount == sCount? NO ✗


Step 7: Slide window to position 6 [b a c]
═══════════════════════════════════════════════════════════════════
Remove s[5]='a': sCount[a]=1
Add s[8]='c': sCount[c]=1

sCount = [a:1, b:1, c:1, rest:0]

Compare: pCount == sCount? YES ✓
Add index 6 to result

result = [0, 6]


Step 8: Slide window to position 7 [a c d]
═══════════════════════════════════════════════════════════════════
Remove s[6]='b': sCount[b]=0
Add s[9]='d': sCount[d]=1

sCount = [a:1, b:0, c:1, d:1, rest:0]

Compare: pCount == sCount? NO ✗


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [0, 6]
═══════════════════════════════════════════════════════════════════

---

🔍 Edge Cases

Case 1: p longer than s
Input: s = "ab", p = "abc"
Output: []
Explanation: No substring of length 3 in s

Case 2: Single character
Input: s = "a", p = "a"
Output: [0]

Case 3: All same characters
Input: s = "aaaa", p = "aa"
Output: [0,1,2]
Explanation: "aa", "aa", "aa"

Case 4: No anagrams
Input: s = "abcd", p = "xyz"
Output: []

Case 5: Entire string is anagram
Input: s = "abc", p = "abc"
Output: [0]

Case 6: Multiple overlapping anagrams
Input: s = "abab", p = "ab"
Output: [0,1,2]

Case 7: p has duplicate characters
Input: s = "cbaebabacd", p = "abbc"
Output: []
Explanation: Need two 'b's

Case 8: s has all characters but wrong frequency
Input: s = "aabbcc", p = "abc"
Output: []
Explanation: Frequencies don't match

---

Common Mistakes

Mistake 1: Not handling p.length > s.length
❌ Wrong: 
    // No check, may cause issues
✓ Right: 
    if (s.length() < p.length()) return result;
Reason: Cannot have substring longer than string

Mistake 2: Wrong window slide indices
❌ Wrong: 
    for (int i = 0; i < s.length(); i++) {
        // Add s[i + p.length()] - out of bounds!
    }
✓ Right: 
    for (int i = p.length(); i < s.length(); i++) {
        // Add s[i], remove s[i - p.length()]
    }
Reason: Must ensure indices are valid

Mistake 3: Comparing maps instead of arrays
❌ Wrong: 
    if (sCount.equals(pCount)) {  // Won't work for arrays
        result.add(i);
    }
✓ Right: 
    if (Arrays.equals(sCount, pCount)) {
        result.add(i);
    }
Reason: Arrays need Arrays.equals()

Mistake 4: Wrong starting index in result
❌ Wrong: 
    result.add(i);  // Wrong index
✓ Right: 
    result.add(i - p.length() + 1);
Reason: i is right end, need left start

Mistake 5: Not handling matches counter correctly
❌ Wrong: 
    if (sCount[rightIdx] == pCount[rightIdx]) {
        matches++;  // Always increment
    }
✓ Right: 
    if (sCount[rightIdx] == pCount[rightIdx]) {
        matches++;
    } else if (sCount[rightIdx] == pCount[rightIdx] + 1) {
        matches--;  // Was matching, now not
    }
Reason: Need to handle both match and unmatch cases

Mistake 6: Forgetting to check first window
❌ Wrong: 
    // Start loop from p.length() without checking first window
✓ Right: 
    // Check first window before sliding
    if (Arrays.equals(pCount, sCount)) {
        result.add(0);
    }
Reason: First window not checked in loop

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n × m)
  Space: O(m)
  Use: Only for understanding

Approach 2: Sliding Window + Array Comparison
  Time: O(n × 26) = O(n)
  Space: O(1)
  Use: Simple and effective

Approach 3: Sliding Window + Counter (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Most optimal, best for interviews

🔑 The Core Insight

Fixed-Size Sliding Window for Anagram Detection:

Anagram Definition:
Two strings are anagrams if they have:
1. Same length (guaranteed by fixed window)
2. Same character frequencies

Sliding Window Optimization:
Instead of recounting each window:
1. Count first window
2. Slide: Remove left char, Add right char
3. Update frequency incrementally
4. Compare frequencies

Three Comparison Methods:

Method 1: Array Comparison (Simple)
- Compare arrays with Arrays.equals()
- Time: O(26) = O(1) per window

Method 2: Counter Optimization (Best)
- Track matches: count of chars with matching frequency
- matches == 26 means anagram
- Update counter as frequencies change
- Time: O(1) per window

Window Sliding Formula:
- Right index: i (current position)
- Left index: i - p.length() (window start)
- Add: s.charAt(i)
- Remove: s.charAt(i - p.length())

🎯 Pattern Recognition

Problem Type: Find All Occurrences with Character Constraint
Core Pattern: Fixed-Size Sliding Window + Frequency Matching

When to Apply:
✓ Finding all substrings matching pattern
✓ Anagram detection problem
✓ Fixed window size (pattern length)
✓ Character frequency matching
✓ Want O(n) time complexity

Key Techniques:
→ Fixed-size sliding window
→ Frequency array (size 26 for lowercase)
→ Incremental frequency updates
→ Efficient comparison (counter method)
→ Track starting indices of matches

Template:
1. Build frequency array for pattern
2. Build frequency for first window
3. Check first window
4. For each remaining position:
   - Slide window (remove left, add right)
   - Update frequencies
   - Check if match
   - Add index if match

Related Problems:
- Permutation in String (LC 567)
- Minimum Window Substring (LC 76)
- Substring with Concatenation of All Words (LC 30)

🧠 Interview Strategy

Step 1: "Need to find all anagrams of p in s"
Step 2: "Fixed window size = p.length"
Step 3: "Use frequency array to track character counts"
Step 4: "Slide window, update frequencies incrementally"
Step 5: "O(n) time with counter optimization"

Key Points to Mention:
- Fixed-size sliding window (not variable)
- Anagram = same character frequencies
- Frequency array of size 26
- Slide window: remove left, add right
- Arrays.equals() or counter for comparison
- Counter method: O(1) comparison vs O(26)
- Return list of starting indices
- O(n) time, O(1) space

---

📝 Quick Revision Notes

🎯 Core Concept:

Fixed-size sliding window (size = p.length) with frequency arrays. Slide window, update frequencies incrementally, check if match.

⚡ Quick Implementation (Array Comparison):

  public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length()) {
      return res;
    }

    int[] scount = new int[26];
    int[] pcount = new int[26];

    // Approach 1 - using freq array and comparisons O(26) every time.
    // for (int i = 0; i < p.length(); i++) {
    // pcount[p.charAt(i) - 'a']++;
    // }

    // for (int i = 0; i < p.length(); i++) {
    // scount[s.charAt(i) - 'a']++;
    // }

    // if (Arrays.equals(scount, pcount)) { // everytime O(26)
    // res.add(0);
    // }

    // int len = p.length();
    // for (int i = len; i < s.length(); i++) {
    // // decrement count of the character that is out of the window
    // scount[s.charAt(i - len) - 'a']--;
    // // increment count of the character that is inside the window now.
    // scount[s.charAt(i) - 'a']++; //

    // if (Arrays.equals(scount, pcount)) {
    // res.add(i - len + 1);
    // }
    // }

    // Approach 2 - lets reduce O(26) with running counter
    for (int i = 0; i < p.length(); i++) {
      pcount[p.charAt(i) - 'a']++;
    }

    for (int i = 0; i < p.length(); i++) {
      scount[s.charAt(i) - 'a']++;
    }

    int matches = 0; // running counter
    for (int i = 0; i < 26; i++) {
      if (scount[i] == pcount[i]) {
        matches++;
      }
    }

    if (matches == 26) {
      res.add(0);
    }

    int len = p.length();
    for (int i = len; i < s.length(); i++) {
      // shrink window
      int leftIndex = s.charAt(i - len) - 'a';
      // decrement matches count if those frequencies are currently equal as we are
      // going to remove the character in next step. Do it before before removal.
      if (scount[leftIndex] == pcount[leftIndex]) {
        matches--;
      }
      // update scount now
      scount[leftIndex]--;
      // increment matches count after the update.
      if (scount[leftIndex] == pcount[leftIndex]) {
        matches++;
      }

      // expand window
      int rightIndex = s.charAt(i) - 'a';
      if (scount[rightIndex] == pcount[rightIndex]) {
        matches--;
      }
      // update scount now
      scount[rightIndex]++;
      // increment matches count after the update.
      if (scount[rightIndex] == pcount[rightIndex]) {
        matches++;
      }

      if (matches == 26) {
        res.add(i - len + 1);
      }
    }

    return res;
  }

🔑 Key Insights:

• Fixed window: Size = p.length (constant)
• Anagram check: Same character frequencies
• Frequency arrays: Size 26 for lowercase letters
• Incremental update: Remove left, add right (O(1))
• Comparison: Arrays.equals() takes O(26) = O(1)
• Starting index: i - p.length() + 1 (i is right end)
• First window: Check before loop starts
• Counter optimization: Track matches for O(1) comparison
• Time: O(n) - single pass with constant work per position
• Space: O(1) - fixed-size arrays

🎪 Memory Aid:

"Fixed window SLIDES, frequencies UPDATE, anagram CHECK!"
Think: "Same length + same frequencies = anagram!"

---

Related Patterns

• Permutation in String (LC 567)
• Minimum Window Substring (LC 76)
• Substring with Concatenation of All Words (LC 30)
• Longest Substring Without Repeating Characters (LC 3)

---

Happy practicing! 🎯