Find All Anagrams in a String

Find All Anagrams in a String is a classic fixed-window question. You hunt for every spot in a big string where a small word appears, just shuffled around. The simple way checks each spot from scratch. The interviewer wants to see if you can slide a window and reuse your work instead. That is the real test here.

🎯 The Problem

You get a long string s and a short string p. Here are the rules.

• Find every starting position in s where a substring is an anagram of p.
• An anagram is the same letters in any order. So abc, bca and cab are anagrams of each other.
• An anagram uses the exact same letters the exact same number of times.
• The matching substring always has the same length as p.
• Return the list of those start positions.

Take s as cbaebabacd and p as abc. The substring at position 0 is cba, the letters a, b, c. That is an anagram, so 0 goes in. The substring at position 6 is bac, same letters again, so 6 goes in too.

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

Explanation:
Substring at index 0 is "cba", an anagram of "abc"
Substring at index 6 is "bac", an anagram of "abc"

Here is the idea as a picture. A window of the same length as p slides across s one step at a time. At each stop we ask if the letters inside match the letters of p.

The window width never changes. It always equals the length of p.

🐢 Approach 1: Sort Every Window (Brute Force)

The idea in one line: slide a window the size of p, then sort each window and compare it to a sorted p.

The idea:

• Take a window the size of p.
• Slide it one step at a time across s.
• Sort the window letters and sort p. If the sorted forms match, it is an anagram.

How it works:

• At each stop, sort the window.
• Compare it with the pre-sorted p.
• Record the start position when they match.

Why it is weak:

• You sort the window again at every position.
• Sorting k letters costs about k log k work each time.
• The total is about O(n times k log k).
• Two neighbour windows share almost all letters, yet you re-sort everything.

Here is the brute-force code for that idea:

def find_anagrams(s, p):
    answer = []
    target = sorted(p)
    size = len(p)
    for i in range(len(s) - size + 1):
        if sorted(s[i:i + size]) == target:
            answer.append(i)
    return answer

⚡ Approach 2: Sliding Window With Counts (Best)

The idea in one line: anagrams only need equal letter counts, so count letters and update only the two that change.

The idea:

• Two strings are anagrams when each letter appears the same number of times in both.
• A count array holds, for each letter, how many times it appears.
• Build one count for p and one for the current window.

How it works:

• As the window slides one step, only two letters change.
• One new letter enters on the right. One old letter leaves on the left.
• Add one for the entering letter. Subtract one for the leaving letter.
• Compare the window count with the p count at each stop. Record a match.

Why it is fast:

• No sorting. Just two small updates per step.
• Each letter enters and leaves the window once.
• The whole scan is O(n).

Here is a dry-run of the count as the window slides. The window is length 3 over cbaebabacd, looking for abc.

Steps to Solve

1. If p is longer than s, there can be no anagram. Return an empty answer.
2. Build a count of every letter in p.
3. Build a count for the first window in s, which is the first len(p) letters.
4. Compare the two counts. If they match, record position 0.
5. Slide the window one step. Add the new right letter to the count. Remove the old left letter from the count.
6. Compare again. If the counts match, record the new start position.
7. Keep sliding until the window reaches the end.

#include <stdio.h>
#include <string.h>

int sameCounts(int a[26], int b[26]) {
    for (int i = 0; i < 26; i++) {
        if (a[i] != b[i]) return 0;
    }
    return 1;
}

void findAnagrams(const char *s, const char *p, int out[], int *outSize) {
    int n = strlen(s), k = strlen(p);
    int idx = 0;
    if (k > n) { *outSize = 0; return; }
    int need[26] = {0}, win[26] = {0};
    for (int i = 0; i < k; i++) {
        need[p[i] - 'a']++;     // count letters of p
        win[s[i] - 'a']++;      // count first window
    }
    if (sameCounts(need, win)) out[idx++] = 0;
    for (int i = k; i < n; i++) {
        win[s[i] - 'a']++;          // add entering letter
        win[s[i - k] - 'a']--;      // remove leaving letter
        if (sameCounts(need, win)) out[idx++] = i - k + 1;
    }
    *outSize = idx;
}

int main(void) {
    const char *s = "cbaebabacd";
    const char *p = "abc";
    int out[10000];
    int outSize = 0;
    findAnagrams(s, p, out, &outSize);
    printf("[");
    for (int i = 0; i < outSize; i++) {
        printf("%d", out[i]);
        if (i < outSize - 1) printf(", ");
    }
    printf("]\n");
    return 0;
}

[0, 6]

#include <iostream>
#include <vector>
#include <string>
#include <array>
using namespace std;

vector<int> findAnagrams(string s, string p) {
    vector<int> result;
    int n = s.size(), k = p.size();
    if (k > n) return result;
    array<int, 26> need{}, win{};
    for (int i = 0; i < k; i++) {
        need[p[i] - 'a']++;     // count letters of p
        win[s[i] - 'a']++;      // count first window
    }
    if (need == win) result.push_back(0);
    for (int i = k; i < n; i++) {
        win[s[i] - 'a']++;          // add entering letter
        win[s[i - k] - 'a']--;      // remove leaving letter
        if (need == win) result.push_back(i - k + 1);
    }
    return result;
}

int main() {
    string s = "cbaebabacd";
    string p = "abc";
    vector<int> result = findAnagrams(s, p);
    cout << "[";
    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i < (int)result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[0, 6]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindAnagrams {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int n = s.length(), k = p.length();
        if (k > n) return result;
        int[] need = new int[26];
        int[] win = new int[26];
        for (int i = 0; i < k; i++) {
            need[p.charAt(i) - 'a']++;   // count letters of p
            win[s.charAt(i) - 'a']++;    // count first window
        }
        if (Arrays.equals(need, win)) result.add(0);
        for (int i = k; i < n; i++) {
            win[s.charAt(i) - 'a']++;        // add entering letter
            win[s.charAt(i - k) - 'a']--;    // remove leaving letter
            if (Arrays.equals(need, win)) result.add(i - k + 1);
        }
        return result;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p));
    }
}

[0, 6]

from collections import Counter


def find_anagrams(s, p):
    n, k = len(s), len(p)
    result = []
    if k > n:
        return result
    need = Counter(p)              # letter counts of p
    win = Counter(s[:k])           # counts of the first window
    if win == need:
        result.append(0)
    for i in range(k, n):
        win[s[i]] += 1             # add entering letter
        win[s[i - k]] -= 1         # remove leaving letter
        if win[s[i - k]] == 0:
            del win[s[i - k]]      # keep the count clean
        if win == need:
            result.append(i - k + 1)
    return result


s = "cbaebabacd"
p = "abc"
print(find_anagrams(s, p))

[0, 6]

function findAnagrams(s, p) {
  const result = [];
  const n = s.length, k = p.length;
  if (k > n) return result;
  const a = "a".charCodeAt(0);
  const need = new Array(26).fill(0);
  const win = new Array(26).fill(0);
  for (let i = 0; i < k; i++) {
    need[p.charCodeAt(i) - a]++;       // count letters of p
    win[s.charCodeAt(i) - a]++;        // count first window
  }
  const equal = () => need.every((v, i) => v === win[i]);
  if (equal()) result.push(0);
  for (let i = k; i < n; i++) {
    win[s.charCodeAt(i) - a]++;        // add entering letter
    win[s.charCodeAt(i - k) - a]--;    // remove leaving letter
    if (equal()) result.push(i - k + 1);
  }
  return result;
}

const s = "cbaebabacd";
const p = "abc";
console.log(findAnagrams(s, p));

[ 0, 6 ]

Let us walk through the Python version line by line and see why each line is there.

The line if k > n: return result handles the easy case. If the pattern is longer than the string, no window can fit. So there can be no anagram.

The line need = Counter(p) builds the target counts. Counter reads p and gives back how many times each letter appears. This is what every window must match.

The line win = Counter(s[:k]) counts the first window. s[:k] is the first k letters of s. We count them the same way.

The check if win == need compares the two counts. Two Counter objects are equal when they hold the same letters with the same counts. If they match, the first window is an anagram, so result.append(0) records position 0.

The loop for i in range(k, n) slides the window. Position i is the new letter entering on the right.

The line win[s[i]] += 1 adds the entering letter to the window count. The line win[s[i - k]] -= 1 removes the letter that just left on the left. These two small updates replace rebuilding the whole count.

The lines if win[s[i - k]] == 0: del win[s[i - k]] keep the count clean. When a letter’s count drops to zero we delete its slot. This matters because Counter equality treats a missing letter and a zero count differently. So we remove the empty slot to keep the compare correct.

The check if win == need compares again after the slide. If they match, result.append(i - k + 1) records the start position of this window.

⏱️ Time and Space Complexity

The brute force sorts each window, so it is slow but uses little extra memory. The sliding window does two updates per step and compares small fixed-size counts. So it runs in one pass. That takes the time from O(n times k log k) down to O(n). The counts hold at most 26 letters, so the extra space is O(1).

🧩 Key Takeaways

• ✅ Two strings are anagrams when each letter appears the same number of times in both.
• ✅ The brute force sorts every window, which costs O(n times k log k) time.
• ✅ Counting letters is faster than sorting, and the counts fit in a fixed array of 26 slots.
• ✅ As the window slides, only two letters change, so you update the count instead of rebuilding it.
• ✅ The whole scan is O(n) time and O(1) extra space.

🚀 What’s Next?

• Sliding Window Maximum
• Max Consecutive Ones III