Course4all

Find All Anagrams in a String

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Sliding Window.

Find All Anagrams in a String

Given strings s and p, return an array of all the start indices of p's anagrams in s.

Visual Representation

s = "cbaebabacd", p = "abc" [c b a] e b a b a c d (Window: {a:1, b:1, c:1}, Matches! Index 0) c [b a e] b a b a c d (Window: {a:1, b:1, e:1}, Mismatch) ... c b a e b a b [a c d] (Wait, missing b! Mismatch)
Medium

Examples

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Approach 1

Level I: Brute Force

Intuition

For every possible substring of s that has the same length as p, check if it's an anagram of p. To check for anagrams, we can sort both strings or compare their character frequency maps.

Thought Process

  1. Iterate through s with a loop from 0 to n - m (where m is p.length()).
  2. Extract the substring of length m.
  3. Compare the substring with p using a frequency map or sorting.
  4. If they match, add the starting index to the result list.
⏱ O(N * M)💾 O(1) - alphabet size (26)

Detailed Dry Run

Start IndexSubstringIs Anagram of "abc"?Result
0"cba"YES[0]
1"bae"NO[0]
6"abc"YES[0, 6]
java
import java.util.*;

public class Main {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (n < m) return result;
        
        int[] pCount = new int[26];
        for (char c : p.toCharArray()) pCount[c - 'a']++;

        for (int i = 0; i <= n - m; i++) {
            int[] sCount = new int[26];
            for (int j = i; j < i + m; j++) {
                sCount[s.charAt(j) - 'a']++;
            }
            if (Arrays.equals(pCount, sCount)) {
                result.add(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc")); // [0, 6]
    }
}
Approach 2

Level II: Optimized Brute Force (O(N * 26))

Intuition

Instead of re-comparing the whole substring or sorting, we can compare the frequency counts of characters. Since the alphabet is small (26), comparing two maps of size 26 is O(26)O(26), which is effectively constant time.

Thought Process

  1. Count character frequencies for p.
  2. Iterate through s and for every window of size m, build the frequency map for that window.
  3. Compare the map with pCount using Arrays.equals (Java) or == (Python/Go).

Pattern: Constant-Time Map Comparison

⏱ O(N * 26) where N is the length of `s`.💾 O(26) for storing frequency counts.
java
public class Main {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (n < m) return res;
        int[] pCount = new int[26];
        for (char c : p.toCharArray()) pCount[c - 'a']++;

        for (int i = 0; i <= n - m; i++) {
            int[] sCount = new int[26];
            for (int j = i; j < i + m; j++) sCount[s.charAt(j) - 'a']++;
            if (java.util.Arrays.equals(pCount, sCount)) res.add(i);
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Since an anagram must have exactly the same length as p, we use a Fixed Size Sliding Window of length m. We maintain frequency counts for both p and the current s window. Instead of re-calculating the frequency map for every window, we 'slide' it: add the incoming character and remove the outgoing one.

Pattern: Fixed Size Sliding Window

  • Init: Fill frequency maps for p and the first m characters of s.
  • Slide: For i from m to n-1:
    1. Add s[i] to sCount.
    2. Remove s[i - m] from sCount.
    3. Compare maps.
⏱ O(N)💾 O(1) - alphabet size (26).

Detailed Dry Run

| Window | Start Index | Added | Removed | Match? | | :--- | :--- | :--- | :--- | :--- | :--- | | [0, 2] | 0 | - | - | YES | | [1, 3] | 1 | 'e' | 'c' | NO | | [6, 8] | 6 | 'c' | 'b' | YES |
java
import java.util.*;

public class Main {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;
        
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(pCount, sCount)) res.add(0);

        for (int i = p.length(); i < s.length(); i++) {
            sCount[s.charAt(i) - 'a']++; // Add right
            sCount[s.charAt(i - p.length()) - 'a']--; // Remove left
            
            if (Arrays.equals(pCount, sCount)) {
                res.add(i - p.length() + 1);
            }
        }
        return res;
    }

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

⚠️ Common Pitfalls & Tips

Be careful with the sliding logic: ensure you add the NEW character and remove the OLD character at the same step to keep the window size constant. Also, check the very first window before the loop starts.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionLongest Repeating Character Replacement
Next Question →Sliding Window Maximum