10.11 Find All Anagrams in a String

10.11.1 Problem Metadata

10.11.2 Description

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consist of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

10.11.3 Examples

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".

10.11.4 Constraints

  • \(1 \le\) s.length, p.length \(\le\) \(2 \times 10^4\)
  • s and p consist of lowercase English letters

10.11.5 Solution 1 - Brute Force with Frequency Map

10.11.5.1 Walkthrough

This solution uses a brute force approach with frequency counting to identify all anagrams. The key insight is that two strings are anagrams if and only if they have identical character frequency distributions.

Core Approach: 1. Create a frequency map for the pattern string p 2. For each possible window of length p.length() in string s: - Create a frequency map for the current window - Compare it with p’s frequency map - If they match, record the starting index

Key Observation: Instead of using HashMap, we use a fixed-size array of length 26 (for lowercase English letters a-z). This provides: - O(1) access time - O(26) comparison time using Arrays.equals() - Constant space overhead

Visual Example with s = “cbaebabacd”, p = “abc”:

Pattern p = "abc" → pFreq = [1,1,1,0,0,...,0]
                            (a=1, b=1, c=1)

Check each window of length 3:

i=0: window = "cba"
  tFreq = [1,1,1,0,0,...,0] (a=1, b=1, c=1)
  Arrays.equals(pFreq, tFreq) → true ✓
  Result: [0]

i=1: window = "bae"
  tFreq = [1,1,0,0,1,...,0] (a=1, b=1, e=1)
  Arrays.equals(pFreq, tFreq) → false
  Result: [0]

i=2: window = "aeb"
  tFreq = [1,1,0,0,1,...,0] (a=1, b=1, e=1)
  Arrays.equals(pFreq, tFreq) → false
  Result: [0]

i=3: window = "eba"
  tFreq = [1,1,0,0,1,...,0] (a=1, b=1, e=1)
  Arrays.equals(pFreq, tFreq) → false
  Result: [0]

i=4: window = "bab"
  tFreq = [1,2,0,0,0,...,0] (a=1, b=2)
  Arrays.equals(pFreq, tFreq) → false
  Result: [0]

i=5: window = "aba"
  tFreq = [2,1,0,0,0,...,0] (a=2, b=1)
  Arrays.equals(pFreq, tFreq) → false
  Result: [0]

i=6: window = "bac"
  tFreq = [1,1,1,0,0,...,0] (a=1, b=1, c=1)
  Arrays.equals(pFreq, tFreq) → true ✓
  Result: [0, 6]

i=7: window = "acd"
  tFreq = [1,0,1,1,0,...,0] (a=1, c=1, d=1)
  Arrays.equals(pFreq, tFreq) → false
  Result: [0, 6]

Final result: [0, 6]

Helper Method - createFreqMap: - Takes a string and creates a frequency array - For each character c, increment freqMap[c - 'a'] - The expression c - 'a' maps ‘a’ to 0, ‘b’ to 1, …, ‘z’ to 25

10.11.5.2 Analysis

  • Time Complexity: O(n × m)
    • n is the length of string s, m is the length of string p
    • Outer loop runs n - m + 1 times, which is O(n)
    • For each iteration, createFreqMap() takes O(m) time to build the frequency array
    • Arrays.equals() takes O(26) which is O(1)
    • Total: O(n) × O(m) = O(n × m)
  • Space Complexity: O(1)
    • Two fixed-size frequency arrays of length 26
    • Output list is not counted in space complexity
    • Total: O(1)

10.11.5.3 Implementation Steps

  1. Create a helper method createFreqMap(String s) that:

    • Initializes an integer array of size 26
    • Iterates through the string and increments freqMap[c - 'a'] for each character
    • Returns the frequency array

  2. Create the frequency map for pattern p using the helper method

  3. Initialize an empty result list to store starting indices

  4. Iterate through string s with index i from 0 to s.length() - p.length():

    • Extract substring from index i to i + p.length()
    • Create frequency map for the substring
    • Compare with p’s frequency map using Arrays.equals()
    • If they match, add index i to the result list

  5. Return the result list

10.11.5.4 Code - Java

public List<Integer> findAnagrams(String s, String p) {
    int[] pFreq = createFreqMap(p);

    List<Integer> result = new ArrayList<>();

    for (int i = 0; i <= s.length() - p.length(); i++) {
        String tstr = s.substring(i, i + p.length());
        int[] tFreq = createFreqMap(tstr);
        if (Arrays.equals(pFreq, tFreq)) {
            result.add(i);
        }
    }

    return result;
}

private int[] createFreqMap(String s) {
    int[] freqMap = new int[26];
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        freqMap[c - 'a']++;
    }

    return freqMap;
}

10.11.6 Solution 2 - Sliding Window with Frequency Map

10.11.6.1 Walkthrough

This solution optimizes the brute force approach by using a sliding window technique. Instead of recreating the frequency map for each window, we maintain a single frequency map and update it incrementally as the window slides.

Core Optimization: - The brute force solution recalculates the entire frequency map for each window (O(m) per window) - The sliding window updates only two characters per slide (O(1) per window)

Algorithm Steps:

  1. Initialize: Create frequency maps for pattern p and the first window of s
  2. Check first window: Compare the two frequency maps
  3. Slide the window: For each subsequent position:
    • Add the new character entering the window on the right
    • Remove the old character leaving the window on the left
    • Compare frequency maps and record index if they match

Key Insight - Window Index Calculation: When we’re at position i in the main loop (where i ranges from len to s.length() - 1): - The window spans from index i - len + 1 to index i (inclusive) - The starting index of this window is i - len + 1

Visual Example with s = “cbaebabacd”, p = “abc”:

Pattern p = "abc" → pFreq = [1,1,1,0,0,...,0]
                            (a=1, b=1, c=1)

Step 1: Initialize first window [0:3) = "cba"
  pFreq = [1,1,1,0,0,...,0]
  wFreq = [1,1,1,0,0,...,0]
  Arrays.equals(pFreq, wFreq) → true ✓
  Result: [0]

Step 2: Slide to i=3 (window [1:4) = "bae")
  Remove s[0]='c': wFreq[2]-- → wFreq = [1,1,0,0,1,...,0]
  Add s[3]='e':    wFreq[4]++ → wFreq = [1,1,0,0,1,...,0]
  Starting index: 3 - 3 + 1 = 1
  Arrays.equals(pFreq, wFreq) → false

Step 3: Slide to i=4 (window [2:5) = "aeb")
  Remove s[1]='b': wFreq[1]-- → wFreq = [1,0,0,0,1,...,0]
  Add s[4]='b':    wFreq[1]++ → wFreq = [1,1,0,0,1,...,0]
  Starting index: 4 - 3 + 1 = 2
  Arrays.equals(pFreq, wFreq) → false

Step 4: Slide to i=5 (window [3:6) = "eba")
  Remove s[2]='a': wFreq[0]-- → wFreq = [0,1,0,0,1,...,0]
  Add s[5]='a':    wFreq[0]++ → wFreq = [1,1,0,0,1,...,0]
  Starting index: 5 - 3 + 1 = 3
  Arrays.equals(pFreq, wFreq) → false

Step 5: Slide to i=6 (window [4:7) = "bab")
  Remove s[3]='e': wFreq[4]-- → wFreq = [1,1,0,0,0,...,0]
  Add s[6]='b':    wFreq[1]++ → wFreq = [1,2,0,0,0,...,0]
  Starting index: 6 - 3 + 1 = 4
  Arrays.equals(pFreq, wFreq) → false

Step 6: Slide to i=7 (window [5:8) = "aba")
  Remove s[4]='b': wFreq[1]-- → wFreq = [1,1,0,0,0,...,0]
  Add s[7]='a':    wFreq[0]++ → wFreq = [2,1,0,0,0,...,0]
  Starting index: 7 - 3 + 1 = 5
  Arrays.equals(pFreq, wFreq) → false

Step 7: Slide to i=8 (window [6:9) = "bac")
  Remove s[5]='a': wFreq[0]-- → wFreq = [1,1,0,0,0,...,0]
  Add s[8]='c':    wFreq[2]++ → wFreq = [1,1,1,0,0,...,0]
  Starting index: 8 - 3 + 1 = 6
  Arrays.equals(pFreq, wFreq) → true ✓
  Result: [0, 6]

Step 8: Slide to i=9 (window [7:10) = "acd")
  Remove s[6]='b': wFreq[1]-- → wFreq = [1,0,1,0,0,...,0]
  Add s[9]='d':    wFreq[3]++ → wFreq = [1,0,1,1,0,...,0]
  Starting index: 9 - 3 + 1 = 7
  Arrays.equals(pFreq, wFreq) → false

Final result: [0, 6]

Why This is Faster: - Brute force: Creates new frequency map for each of n windows → n × m operations - Sliding window: Updates existing frequency map with 2 operations per window → 2n operations

10.11.6.2 Analysis

  • Time Complexity: O(n + m)
    • Building frequency map for p: O(m)
    • Building frequency map for first window: O(m)
    • Sliding the window: n - m iterations, each with:
      • Two frequency updates: O(1)
      • Array comparison: O(26) = O(1)
    • Total: O(m) + O(m) + O(n - m) × O(1) = O(n + m)
  • Space Complexity: O(1)
    • Two fixed-size frequency arrays of length 26
    • Output list is not counted in space complexity
    • Total: O(1)

Comparison with Solution 1: - Solution 1 (Brute Force): O(n × m) time - Solution 2 (Sliding Window): O(n + m) time - For large inputs where n is much larger than m, this is a significant improvement

10.11.6.3 Implementation Steps

  1. Initialize two frequency arrays: pFreq for pattern p and wFreq for the sliding window

  2. Edge case check: If s.length() < p.length(), return empty list immediately

  3. Build initial frequency maps:

    • Iterate through the first len characters
    • For each character at position i, increment both pFreq[p.charAt(i) - 'a'] and wFreq[s.charAt(i) - 'a']

  4. Check first window: If Arrays.equals(pFreq, wFreq), add index 0 to result

  5. Slide the window: For i from len to s.length() - 1:

    • Add new character: increment wFreq[s.charAt(i) - 'a']
    • Remove old character: decrement wFreq[s.charAt(i - len) - 'a']
    • If frequency maps match, add starting index i - len + 1 to result

  6. Return the result list

10.11.6.4 Code - Java

public List<Integer> findAnagrams(String s, String p) {
    int[] pFreq = new int[26];
    int[] wFreq = new int[26];
    int len = p.length();
    List<Integer> result = new ArrayList<>();

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

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

    // Check if first window is anagram
    if (Arrays.equals(pFreq, wFreq)) {
        result.add(0);
    }

    for (int i = len; i < s.length(); i++) {
        char newC = s.charAt(i);
        char oldC = s.charAt(i - len);
        // Update freq for new right border of window
        wFreq[newC - 'a']++;
        // Update freq for old left border of window
        wFreq[oldC - 'a']--;
        if (Arrays.equals(pFreq, wFreq)) {
            result.add(i - len + 1);
        }
    }

    return result;
}