Log inSign up
mediumleetcodeNot Started

Find All Anagrams in a String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1 · Example:

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 · Example:

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

Constraints:

  • 1 <= s.length, p.length <= 3 * 104
  • s and p consist of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the fixed-length sliding window state transition.
  • Implement O(1) auxiliary space frequency comparison.
  • Optimize window checks using differential match counters.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • When finding all substrings that are permutations or anagrams of a pattern string.
  • When pattern length is fixed and character counts determine validity.

Algorithmic Decision Tree:

  • Fixed Size Sliding Window
  • Anagram Frequency Matching

Connected Patterns:

Permutation in StringMinimum Window SubstringLongest Substring Without Repeating Characters

1. Substring Sorting Brute Force

Intuition

Sort string p once. Then iterate index i from 0 to s.length - p.length. Extract the substring s.substr(i, p.length), sort its characters, and compare with sorted p. If they are identical, record index i.

When to apply: As an initial baseline concept before explaining sliding window.

Algorithm

  1. If s.length < p.length, return empty list.
  2. Sort p to get sortedP.
  3. Loop i from 0 to s.length - p.length:
  4. Extract substring of length p.length starting at i.
  5. Sort the substring.
  6. If sorted substring equals sortedP, push i to results.
  7. Return results list.

Substring Sorting Brute Force

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [c, b, a, e, b, a, b, a, c, d]
Current operationSTEP 1 OF 6
Observation: Target $p = 'abc'$ has length $M = 3$ and sorts to 'abc'
Visual state
Values and pointers at this exact step
array
S
c
b
a
e
b
a
b
a
c
d
0
↑ L=0
1
2
↑ R=2 ('cba')
3
4
5
6
7
8
9
Variables at this step
window
cba
sorted
abc
targetSorted
abc
match
true
results
[0]
Check / comparison
p = 'abc' sorts to 'abc'. Window s[0..2] = 'cba' sorts to 'abc'.
Decision / next transition
'abc' == 'abc'! Anagram match at index 0. Append 0 to results: [0].
Why this step matters

Observation: Target p = abc has length M = 3 and sorts to 'abc'. Inspect window s[0..2] = 'cba'.

Decision: Sorting 'cba' yields 'abc'. Exactly matches target; record start index 0.

Invariant: Two strings are anagrams if and only if their sorted versions are identical.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 std::vector<int> findAnagrams(std::string s, std::string p) {
9 std::vector<int> res;
10 int n = s.size(), m = p.size();
11 if (n < m) return res;
12
13 std::string sortedP = p;
14 std::sort(sortedP.begin(), sortedP.end());
15
16 for (int i = 0; i <= n - m; ++i) {
17 std::string sub = s.substr(i, m);
18 std::sort(sub.begin(), sub.end());
19 if (sub == sortedP) {
20 res.push_back(i);
21 }
22 }
23 return res;
24 }
25};
26
27int main() {
28 Solution sol;
29 auto ans = sol.findAnagrams("cbaebabacd", "abc");
30 for (int x : ans) std::cout << x << " "; // 0 6
31 std::cout << std::endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M log M) — Extracting and sorting M characters for each of the (N - M + 1) windows takes O(N * M log M).
  • Space complexity: O(M) for substring copies

Why Brute Force Doesn't Scale:

Tracking the number of matching frequencies avoids even the 26-element array loop.

Using two 26-element primitive arrays requires O(1) space and zero heap allocations.

2. Sliding Window with 26-Array Comparison

Intuition

Build frequency arrays pCount and sCount of size 26. Populate pCount and the initial window s[0...m-1] in sCount. Compare arrays: if identical, index 0 is valid. Then slide window from index m to n - 1: add incoming character s[i] to sCount and subtract outgoing character s[i - m] from sCount. Check if sCount == pCount at each step.

When to apply: Industry standard interview approach balancing clarity and optimal time complexity.

Algorithm

  1. If s.length < p.length, return empty list.
  2. Populate pCount and initial sCount for first m characters.
  3. If sCount == pCount, add 0 to result.
  4. For i from m to n - 1:
  5. Increment sCount[s[i] - 'a'].
  6. Decrement sCount[s[i - m] - 'a'].
  7. If sCount == pCount, add i - m + 1 to result.
  8. Return result.

Sliding Window with 26-Array Comparison

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [c, b, a, e, b, a, b, a, c, d]
Current operationSTEP 1 OF 6
Observation: Initialize frequency vector pCount for target and sCount for first window
Visual state
Values and pointers at this exact step
array
S
c
b
a
e
b
a
b
a
c
d
0
↑ L=0
1
2
↑ R=2
3
4
5
6
7
8
9
Variables at this step
L
0
R
2
pCount
{"a":1,"b":1,"c":1}
sCount
{"a":1,"b":1,"c":1}
match
true
results
[0]
Check / comparison
pCount: {a:1, b:1, c:1}. sCount for [0..2]: {a:1, b:1, c:1}.
Decision / next transition
Compare 26-array: Arrays equal! Record index 0. Results: [0].
Why this step matters

Observation: Initialize frequency vector pCount for target and sCount for first window.

Decision: Both vectors have a:1, b:1, c:1 and zeros elsewhere. Equality confirmed; add 0 to results.

Invariant: Frequency array comparison takes O(26) = O(1) time.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<int> findAnagrams(std::string s, std::string p) {
8 std::vector<int> res;
9 int n = s.size(), m = p.size();
10 if (n < m) return res;
11
12 std::vector<int> pCount(26, 0), sCount(26, 0);
13 for (int i = 0; i < m; ++i) {
14 pCount[p[i] - 'a']++;
15 sCount[s[i] - 'a']++;
16 }
17
18 if (pCount == sCount) res.push_back(0);
19
20 for (int i = m; i < n; ++i) {
21 sCount[s[i] - 'a']++;
22 sCount[s[i - m] - 'a']--;
23
24 if (sCount == pCount) {
25 res.push_back(i - m + 1);
26 }
27 }
28 return res;
29 }
30};
31
32int main() {
33 Solution sol;
34 auto ans = sol.findAnagrams("cbaebabacd", "abc");
35 for (int x : ans) std::cout << x << " "; // 0 6
36 std::cout << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(26 * N) = O(N) — Each of the N window slides performs an O(26) array comparison, which is strictly O(N).
  • Space complexity: O(1) (fixed 26-length arrays)

3. Sliding Window with Matches Tracker (O(1) per step)

Intuition

Maintain a count variable matches initialized to the number of characters (out of 26) where sCount[c] == pCount[c]. When sliding the window, adjust matches when incrementing the incoming character and decrementing the outgoing character. If matches == 26, record the start index.

When to apply: When maximum constant-factor runtime performance is required.

Algorithm

  1. Initialize pCount and sCount arrays of size 26.
  2. Populate initial window and calculate initial matches (count of characters with pCount[i] == sCount[i]).
  3. Slide window from i = 0 to n - 1:
  4. Update incoming character right = s[i]: adjust matches before and after changing count.
  5. If window size exceeds m, update outgoing character left = s[i - m]: adjust matches.
  6. If matches == 26, add i - m + 1 to results.
  7. Return collected indices.

Fixed-Length Sliding Window Anagram Collector

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [c, b, a, e, b, a, b, a, c, d]
Current operationSTEP 1 OF 6
Observation: Window length is p
Visual state
Values and pointers at this exact step
array
S
c
b
a
e
b
a
b
a
c
d
0
↑ L=0
1
2
↑ R=2 (Window: "cba")
3
4
5
6
7
8
9
Variables at this step
pCounts
{"a":1,"b":1,"c":1}
windowCounts
{"a":1,"b":1,"c":1}
match
true
indices
[0]
Why this step matters

Observation: Window length is p.length = 3. First window [0, 2] is "cba".

Decision: Frequency of "cba" exactly matches p = "abc". Record starting index 0.

Invariant: Window size remains strictly 3.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<int> findAnagrams(std::string s, std::string p) {
8 std::vector<int> res;
9 int n = s.size(), m = p.size();
10 if (n < m) return res;
11
12 std::vector<int> pCount(26, 0), sCount(26, 0);
13 for (int i = 0; i < m; ++i) {
14 pCount[p[i] - 'a']++;
15 sCount[s[i] - 'a']++;
16 }
17
18 int matches = 0;
19 for (int i = 0; i < 26; ++i) {
20 if (pCount[i] == sCount[i]) matches++;
21 }
22
23 if (matches == 26) res.push_back(0);
24
25 for (int i = m; i < n; ++i) {
26 int inChar = s[i] - 'a';
27 int outChar = s[i - m] - 'a';
28
29 // Add incoming char
30 sCount[inChar]++;
31 if (sCount[inChar] == pCount[inChar]) {
32 matches++;
33 } else if (sCount[inChar] == pCount[inChar] + 1) {
34 matches--;
35 }
36
37 // Remove outgoing char
38 sCount[outChar]--;
39 if (sCount[outChar] == pCount[outChar]) {
40 matches++;
41 } else if (sCount[outChar] == pCount[outChar] - 1) {
42 matches--;
43 }
44
45 if (matches == 26) {
46 res.push_back(i - m + 1);
47 }
48 }
49 return res;
50 }
51};
52
53int main() {
54 Solution sol;
55 auto ans = sol.findAnagrams("abab", "ab");
56 for (int x : ans) std::cout << x << " "; // 0 1 2
57 std::cout << std::endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N) — Each character addition and removal performs only constant number of integer operations.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force Substring SortingO((N - M + 1) * M log M)O(M)Conceptually simplest.Extremely slow due to repeatedly sorting M characters for each starting index.
2.Sliding Window with 26-Array Equality CheckO(26 * N) = O(N)O(1) (fixed 26-size arrays)Clean, intuitive, and highly robust in interviews.Compares 26 values at each step.
3.Sliding Window with Matches CounterOptimalO(N) strictlyO(1) extra spaceChecks anagram status in O(1) per step by tracking exact matching character counts (0 to 26).Slightly more bookkeeping logic.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using variable window logic instead of strict fixed window of length p.length.

Pitfall 2:

Forgetting to decrement the count of the character falling out of the window.

Crucial Edge Cases to Validate:

  • s.length < p.length: Return empty list immediately since an anagram of p cannot fit in s.
  • s and p have identical lengths: Evaluated in single step, returns [0] if anagram or [] if not.
  • p contains duplicate characters (e.g., aa): Frequency arrays track exact multiplicity of each character.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by establishing that anagrams require identical length and character counts, framing it immediately as a fixed sliding window.
  2. Proactively offer the matches counter optimization to show deep awareness of constant-time refinements.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the window size strictly equal to p.length?

Back to DSA Sheet