Skip to main content
CodePeet

Find All Anagrams in a String

Try it yourself
MediumProblemExternal link

Description

You get two strings, s and p. Return every index i where an anagram of p starts in s: the len(p) letters from i on are the letters of p, each the same number of times, in any order.

You may return the indices in any order.

Examples

Example 1

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

Output: [0,6]

Explanation: The window at 0 is "cba" and the window at 6 is "bac"; both are anagrams of "abc".

Example 2

Input: s = "abab", p = "ab"

Output: [0,1,2]

Explanation: The windows at 0, 1 and 2 are "ab", "ba" and "ab"; each is an anagram of "ab".

Constraints

  • 1 ≤ s.length, p.length ≤ 3 × 10^4
  • s and p consist of lowercase English letters

Editorial

Brute Force

Intuition

Two strings are anagrams exactly when every letter appears the same number of times in both. So count the letters of p once. Then, for every start i, count the letters of the len(p) characters from i and compare the two counts.

Step-by-Step Explanation

Let's check every window of 3 in s = "cbaebabacd" against p = "abc" (a:1 b:1 c:1):

  1. "cba": a:1 b:1 c:1 → an anagram, record 0
  2. "bae": a:1 b:1 e:1
  3. "aeb": a:1 b:1 e:1
  4. "eba": a:1 b:1 e:1
  5. "bab": a:1 b:2
  6. "aba": a:2 b:1
  7. "bac": a:1 b:1 c:1 → an anagram, record 6
  8. "acd": a:1 c:1 d:1

The answer is [0, 6]. Every window was counted from scratch.

Count Every Window From Scratch — Each step counts one whole window again and compares it with p's counts. Green windows are anagrams.

Algorithm

  1. Count the letters of p into need.
  2. For each start from 0 to len(s) − len(p):
    • count the letters of s[start : start + len(p)] into a fresh have;
    • if have == need, record start.
  3. Return the recorded starts.

Code

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int k = p.size();
        vector<int> need(26, 0), starts;
        for (char ch : p) need[ch - 'a']++;
        for (int start = 0; start + k <= (int)s.size(); start++) {
            vector<int> have(26, 0);
            for (int i = start; i < start + k; i++) {
                have[s[i] - 'a']++;             // count the whole window again
            }
            if (have == need) starts.push_back(start);
        }
        return starts;
    }
};

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        k = len(p)
        need = [0] * 26
        for ch in p:
            need[ord(ch) - 97] += 1
        starts = []
        for start in range(len(s) - k + 1):
            have = [0] * 26
            for i in range(start, start + k):
                have[ord(s[i]) - 97] += 1       # count the whole window again
            if have == need:
                starts.append(start)
        return starts

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int k = p.length();
        int[] need = new int[26];
        for (char ch : p.toCharArray()) need[ch - 'a']++;
        List<Integer> starts = new ArrayList<>();
        for (int start = 0; start + k <= s.length(); start++) {
            int[] have = new int[26];
            for (int i = start; i < start + k; i++) {
                have[s.charAt(i) - 'a']++;      // count the whole window again
            }
            if (Arrays.equals(have, need)) starts.add(start);
        }
        return starts;
    }
}

var findAnagrams = function(s, p) {
    const k = p.length;
    const need = new Array(26).fill(0);
    for (const ch of p) need[ch.charCodeAt(0) - 97]++;
    const starts = [];
    for (let start = 0; start + k <= s.length; start++) {
        const have = new Array(26).fill(0);
        for (let i = start; i < start + k; i++) {
            have[s.charCodeAt(i) - 97]++;       // count the whole window again
        }
        if (have.every((count, c) => count === need[c])) starts.push(start);
    }
    return starts;
};

Complexity Analysis

Time Complexity: O(n · k), with n = len(s) and k = len(p)

There are n − k + 1 windows, and each is counted letter by letter.

Space Complexity: O(1)

Two arrays of 26 counts (the answer list aside).

Why This Approach Is Not Efficient

With s of 3 × 10^4 letters and p of 1.5 × 10^4, that's 15,001 windows of 15,000 letters: about 2.25 × 10^8 letters counted.

And neighbouring windows share all but two letters. Moving the window one step right adds one letter on the right and drops one on the left, so the counts can be updated instead of rebuilt.

Better Approach - Sliding Window with Letter Counts

Intuition

Keep the counts of the current window in have. When the window moves one step right, add one to the letter entering, s[right], and take one from the letter leaving, s[right - k]. Once the window is full (right >= k - 1), compare have with need.

Step-by-Step Explanation

Let's slide a window of 3 over s = "cbaebabacd":

  1. Count the first window, "cba": a:1 b:1 c:1. It equals p's counts: record 0.
  2. e enters, c leaves: a:1 b:1 e:1
  3. b enters, b leaves: a:1 b:1 e:1
  4. a enters, a leaves: a:1 b:1 e:1
  5. b enters, e leaves: a:1 b:2
  6. a enters, b leaves: a:2 b:1
  7. c enters, a leaves: a:1 b:1 c:1 → record 6
  8. d enters, b leaves: a:1 c:1 d:1

The answer is [0, 6], and each step changed just two counts.

Slide the Window, Update Two Counts — The glowing letter enters and the amber one leaves; only their counts change. Then all 26 counts are compared with p's.

Algorithm

  1. If p is longer than s, return an empty list.
  2. Count p into need; start have at all zeros.
  3. For each right from 0 to len(s) − 1:
    • add one to have[s[right]];
    • if right >= k, take one from have[s[right - k]];
    • if right >= k - 1 and have == need, record right - k + 1.
  4. Return the recorded starts.

Code

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int k = p.size();
        if (k > (int)s.size()) return {};
        vector<int> need(26, 0), have(26, 0), starts;
        for (char ch : p) need[ch - 'a']++;
        for (int right = 0; right < (int)s.size(); right++) {
            have[s[right] - 'a']++;             // the letter entering
            if (right >= k) have[s[right - k] - 'a']--;   // the letter leaving
            if (right >= k - 1 && have == need) {         // compare all 26 counts
                starts.push_back(right - k + 1);
            }
        }
        return starts;
    }
};

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        k = len(p)
        if k > len(s):
            return []
        need, have = [0] * 26, [0] * 26
        for ch in p:
            need[ord(ch) - 97] += 1
        starts = []
        for right in range(len(s)):
            have[ord(s[right]) - 97] += 1           # the letter entering
            if right >= k:
                have[ord(s[right - k]) - 97] -= 1   # the letter leaving
            if right >= k - 1 and have == need:     # compare all 26 counts
                starts.append(right - k + 1)
        return starts

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int k = p.length();
        List<Integer> starts = new ArrayList<>();
        if (k > s.length()) return starts;
        int[] need = new int[26], have = new int[26];
        for (char ch : p.toCharArray()) need[ch - 'a']++;
        for (int right = 0; right < s.length(); right++) {
            have[s.charAt(right) - 'a']++;              // the letter entering
            if (right >= k) have[s.charAt(right - k) - 'a']--;   // the letter leaving
            if (right >= k - 1 && Arrays.equals(have, need)) {    // compare all 26 counts
                starts.add(right - k + 1);
            }
        }
        return starts;
    }
}

var findAnagrams = function(s, p) {
    const k = p.length;
    if (k > s.length) return [];
    const need = new Array(26).fill(0), have = new Array(26).fill(0);
    for (const ch of p) need[ch.charCodeAt(0) - 97]++;
    const starts = [];
    for (let right = 0; right < s.length; right++) {
        have[s.charCodeAt(right) - 97]++;               // the letter entering
        if (right >= k) have[s.charCodeAt(right - k) - 97]--;   // the letter leaving
        if (right >= k - 1 && have.every((count, c) => count === need[c])) {   // compare all 26 counts
            starts.push(right - k + 1);
        }
    }
    return starts;
};

Complexity Analysis

Time Complexity: O(26 · n)

Two count updates per step, then a comparison of 26 counts.

Space Complexity: O(1)

Two arrays of 26 counts.

Why This Approach Is Not Efficient

It's fast enough here: 26 comparisons per step is a constant. But it's wasted work, because only two counts changed and the comparison looks at all 26. With a larger alphabet (all of Unicode, say), every step would cost the whole alphabet.

Instead, keep track of how many letters agree. A step changes two counts, so it can change that number only through those two letters.

Optimal Approach - Sliding Window with a Match Counter

Intuition

Keep matches: how many of the 26 letters have the same count in the window as in p. At the start (an empty window) that's every letter p doesn't use.

When a letter's count changes, it can only move that letter in or out of agreement. So before the change, if it agreed, take one from matches; after the change, if it agrees, add one. Each step settles its two letters this way, and the window is an anagram exactly when matches is 26.

matches can't reach 26 too early, either: before the window holds len(p) letters, its counts add up to less than p's, so some letter still disagrees.

Step-by-Step Explanation

Let's trace s = "cbaebabacd", p = "abc". The letters a, b and c start out disagreeing (p has one of each, the empty window none), so matches starts at 23:

  1. In the first window, "cba", every letter's count equals p's, so matches = 26. All 26 agree, so record 0.
  2. e enters and its count goes 0 → 1, so e no longer agrees (matches − 1). c leaves and its count goes 1 → 0, so c no longer agrees (matches − 1).
  3. b enters and its count goes 1 → 2, so b no longer agrees (matches − 1). b leaves and its count goes 2 → 1, which is p's count, so b now agrees (matches + 1).
  4. a enters and its count goes 1 → 2, so a no longer agrees (matches − 1). a leaves and its count goes 2 → 1, which is p's count, so a now agrees (matches + 1).
  5. b enters and its count goes 1 → 2, so b no longer agrees (matches − 1). e leaves and its count goes 1 → 0, which is p's count, so e now agrees (matches + 1).
  6. a enters and its count goes 1 → 2, so a no longer agrees (matches − 1). b leaves and its count goes 2 → 1, which is p's count, so b now agrees (matches + 1).
  7. c enters and its count goes 0 → 1, which is p's count, so c now agrees (matches + 1). a leaves and its count goes 2 → 1, which is p's count, so a now agrees (matches + 1). All 26 agree, so record 6.
  8. d enters and its count goes 0 → 1, so d no longer agrees (matches − 1). b leaves and its count goes 1 → 0, so b no longer agrees (matches − 1).

The answer is [0, 6].

Count How Many Letters Agree — The glowing letter enters and the amber one leaves. matches counts the letters whose counts agree with p; green means all 26 do.

Algorithm

  1. If p is longer than s, return an empty list.
  2. Count p into need; start have at all zeros and matches at the number of letters where have[c] == need[c].
  3. For each right, add s[right] and, if right >= k, remove s[right - k]. For each change: if the letter agreed before, take one from matches; if it agrees after, add one.
  4. Whenever matches == 26, record right - k + 1.

Code

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int k = p.size();
        if (k > (int)s.size()) return {};
        vector<int> need(26, 0), have(26, 0), starts;
        for (char ch : p) need[ch - 'a']++;
        int matches = 0;                        // letters whose counts agree
        for (int c = 0; c < 26; c++) {
            if (have[c] == need[c]) matches++;
        }
        for (int right = 0; right < (int)s.size(); right++) {
            int c = s[right] - 'a';             // the letter entering
            if (have[c] == need[c]) matches--;
            have[c]++;
            if (have[c] == need[c]) matches++;
            if (right >= k) {
                c = s[right - k] - 'a';         // the letter leaving
                if (have[c] == need[c]) matches--;
                have[c]--;
                if (have[c] == need[c]) matches++;
            }
            if (matches == 26) starts.push_back(right - k + 1);   // every letter agrees
        }
        return starts;
    }
};

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        k = len(p)
        if k > len(s):
            return []
        need, have = [0] * 26, [0] * 26
        for ch in p:
            need[ord(ch) - 97] += 1
        matches = sum(1 for c in range(26) if have[c] == need[c])   # letters whose counts agree
        starts = []
        for right in range(len(s)):
            c = ord(s[right]) - 97              # the letter entering
            if have[c] == need[c]:
                matches -= 1
            have[c] += 1
            if have[c] == need[c]:
                matches += 1
            if right >= k:
                c = ord(s[right - k]) - 97      # the letter leaving
                if have[c] == need[c]:
                    matches -= 1
                have[c] -= 1
                if have[c] == need[c]:
                    matches += 1
            if matches == 26:                   # every letter agrees
                starts.append(right - k + 1)
        return starts

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int k = p.length();
        List<Integer> starts = new ArrayList<>();
        if (k > s.length()) return starts;
        int[] need = new int[26], have = new int[26];
        for (char ch : p.toCharArray()) need[ch - 'a']++;
        int matches = 0;                        // letters whose counts agree
        for (int c = 0; c < 26; c++) {
            if (have[c] == need[c]) matches++;
        }
        for (int right = 0; right < s.length(); right++) {
            int c = s.charAt(right) - 'a';      // the letter entering
            if (have[c] == need[c]) matches--;
            have[c]++;
            if (have[c] == need[c]) matches++;
            if (right >= k) {
                c = s.charAt(right - k) - 'a';  // the letter leaving
                if (have[c] == need[c]) matches--;
                have[c]--;
                if (have[c] == need[c]) matches++;
            }
            if (matches == 26) starts.add(right - k + 1);   // every letter agrees
        }
        return starts;
    }
}

var findAnagrams = function(s, p) {
    const k = p.length;
    if (k > s.length) return [];
    const need = new Array(26).fill(0), have = new Array(26).fill(0);
    for (const ch of p) need[ch.charCodeAt(0) - 97]++;
    let matches = 0;                            // letters whose counts agree
    for (let c = 0; c < 26; c++) {
        if (have[c] === need[c]) matches++;
    }
    const starts = [];
    for (let right = 0; right < s.length; right++) {
        let c = s.charCodeAt(right) - 97;       // the letter entering
        if (have[c] === need[c]) matches--;
        have[c]++;
        if (have[c] === need[c]) matches++;
        if (right >= k) {
            c = s.charCodeAt(right - k) - 97;   // the letter leaving
            if (have[c] === need[c]) matches--;
            have[c]--;
            if (have[c] === need[c]) matches++;
        }
        if (matches === 26) starts.push(right - k + 1);   // every letter agrees
    }
    return starts;
};

Complexity Analysis

Time Complexity: O(n + 26)

A constant amount of work per letter of s, plus the 26 starting comparisons.

Space Complexity: O(1)

Two arrays of 26 counts and one counter.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Only counting letters that start to agree. if have[c] == need[c]: matches += 1

On s = "ab", p = "a" it returns [0, 1]; the answer is [0]. A letter that agreed before a change stops agreeing after it, and matches has to drop. Counting only the letters that start to agree lets matches climb past the truth, so windows that aren't anagrams get recorded.

Forgetting to remove the leaving letter. for right in range(len(s)): # adds s[right], never removes s[right - k]

On s = "baab", p = "ab" it returns [0]; the answer is [0, 2]. Without removing the letter that slides out, the counts keep growing: after the first window they hold more letters than p has, so they never match again.

Comparing sets of letters, not counts. if set(s[i:i + k]) == set(p)

On s = "aab", p = "abb" it returns [0]; the answer is []. An anagram has the same letters the same number of times. "aab" and "abb" use the same set of letters, {a, b}, and still aren't anagrams. Compare counts.

Where This Pattern Is Taught

This problem practises a fixed-size sliding window that carries letter counts, and the matches counter that makes each step O(1). It's taught in Introduction to Sliding Window, along with Permutation in String, the same loop stopped at the first anagram.