Find All Anagrams in a String

Master this topic with zero to advance depth.

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

Iterate through s with a loop from 0 to n - m (where m is p.length()).
Extract the substring of length m.
Compare the substring with p using a frequency map or sorting.
If they match, add the starting index to the result list.

⏱ O(N * M)💾 O(1) - alphabet size (26)

Detailed Dry Run

Start Index	Substring	Is 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)$ , which is effectively constant time.

Thought Process

Count character frequencies for p.
Iterate through s and for every window of size m, build the frequency map for that window.
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.

← Previous QuestionLongest Repeating Character Replacement

Next Question →Sliding Window Maximum

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.