Find All Anagrams in a String
Find All Anagrams in a String is a medium arrays & hashing problem solved with the sliding window · fixed pattern.
The best approach, optimal (fixed sliding window with a match counter), runs in O(n + m) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recount every window) up.
Problem
You are given two lowercase strings s and p. Find every position in s where a substring of length p.length starts that is an anagram of p, meaning it contains exactly the same letters as p with the same counts, in any order.
Return the list of those starting indices in increasing order.
Examples
Example 1
- Input
s = "tablebatcab", p = "abt"- Output
[0, 5]- Why
- The window starting at 0 is "tab" and the window starting at 5 is "bat"; both use the letters a, b, t once.
Example 2
- Input
s = "aaaa", p = "aa"- Output
[0, 1, 2]- Why
- Every window of length 2 is "aa", and windows may overlap.
Example 3
- Input
s = "xy", p = "xyz"- Output
[]- Why
- p is longer than s, so no window fits.
Constraints
1 <= s.length, p.length <= 3 * 10^4sandpconsist of lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (recount every window) | O(n · m) | O(1) |
| Optimal (fixed sliding window with a match counter) | O(n + m) | O(1) |
1Brute force (recount every window)
O(n · m)There are n - m + 1 windows, each counted in O(m).O(1)Two arrays of 26 counts (the output list aside).Count the letters of p once. For every start index of a window of length m = p.length in s, count that window's letters from scratch and compare the two count arrays.
- If m > n, return an empty list.
- need[26] = letter counts of p.
- For each start i from 0 to n - m: build have[26] from s[i..i+m) and add i if have equals need.
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int n = s.length(), m = p.length();
if (m > n) return result;
int[] need = new int[26];
for (int i = 0; i < m; i++) need[p.charAt(i) - 'a']++;
for (int i = 0; i + m <= n; i++) {
int[] have = new int[26];
for (int j = i; j < i + m; j++) have[s.charAt(j) - 'a']++;
if (Arrays.equals(have, need)) result.add(i);
}
return result;
}
}class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(s), len(p)
result = []
if m > n:
return result
need = [0] * 26
for ch in p:
need[ord(ch) - ord('a')] += 1
for i in range(n - m + 1):
have = [0] * 26
for j in range(i, i + m):
have[ord(s[j]) - ord('a')] += 1
if have == need:
result.append(i)
return resultclass Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
int n = s.size(), m = p.size();
if (m > n) return result;
vector<int> need(26, 0);
for (char ch : p) need[ch - 'a']++;
for (int i = 0; i + m <= n; i++) {
vector<int> have(26, 0);
for (int j = i; j < i + m; j++) have[s[j] - 'a']++;
if (have == need) result.push_back(i);
}
return result;
}
};function findAnagrams(s, p) {
const n = s.length, m = p.length;
const result = [];
if (m > n) return result;
const need = new Array(26).fill(0);
for (let i = 0; i < m; i++) need[p.charCodeAt(i) - 97]++;
for (let i = 0; i + m <= n; i++) {
const have = new Array(26).fill(0);
for (let j = i; j < i + m; j++) have[s.charCodeAt(j) - 97]++;
let same = true;
for (let k = 0; k < 26; k++) {
if (have[k] !== need[k]) { same = false; break; }
}
if (same) result.push(i);
}
return result;
}2Optimal (fixed sliding window with a match counter)
O(n + m)p is counted once and every index of s enters and leaves the window once.O(1)One array of 26 counts and an integer (the output list aside).Slide a window of length m over s and keep one array diff[c] = count in window - count in p, plus zeros, the number of letters whose diff is 0. Each step changes two entries, and updating zeros for those two is O(1). The window is an anagram exactly when all 26 diffs are 0.
- If m > n, return an empty list.
- diff[c] = -(count of c in p); zeros = number of c with diff[c] == 0.
- Define add(c, d): if diff[c] == 0 then zeros--; diff[c] += d; if diff[c] == 0 then zeros++.
- For i from 0 to n - 1: add(s[i], +1); if i >= m, add(s[i - m], -1).
- If i >= m - 1 and zeros == 26, record i - m + 1.
class Solution {
private int[] diff;
private int zeros;
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int n = s.length(), m = p.length();
if (m > n) return result;
diff = new int[26];
for (int i = 0; i < m; i++) diff[p.charAt(i) - 'a']--;
zeros = 0;
for (int c = 0; c < 26; c++) if (diff[c] == 0) zeros++;
for (int i = 0; i < n; i++) {
add(s.charAt(i) - 'a', 1);
if (i >= m) add(s.charAt(i - m) - 'a', -1);
if (i >= m - 1 && zeros == 26) result.add(i - m + 1);
}
return result;
}
private void add(int c, int d) {
if (diff[c] == 0) zeros--;
diff[c] += d;
if (diff[c] == 0) zeros++;
}
}class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(s), len(p)
result = []
if m > n:
return result
diff = [0] * 26
for ch in p:
diff[ord(ch) - ord('a')] -= 1
zeros = sum(1 for d in diff if d == 0)
def add(c: int, d: int) -> None:
nonlocal zeros
if diff[c] == 0:
zeros -= 1
diff[c] += d
if diff[c] == 0:
zeros += 1
for i in range(n):
add(ord(s[i]) - ord('a'), 1)
if i >= m:
add(ord(s[i - m]) - ord('a'), -1)
if i >= m - 1 and zeros == 26:
result.append(i - m + 1)
return resultclass Solution {
int diff[26];
int zeros = 0;
void add(int c, int d) {
if (diff[c] == 0) zeros--;
diff[c] += d;
if (diff[c] == 0) zeros++;
}
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
int n = s.size(), m = p.size();
if (m > n) return result;
for (int c = 0; c < 26; c++) diff[c] = 0;
for (char ch : p) diff[ch - 'a']--;
zeros = 0;
for (int c = 0; c < 26; c++) if (diff[c] == 0) zeros++;
for (int i = 0; i < n; i++) {
add(s[i] - 'a', 1);
if (i >= m) add(s[i - m] - 'a', -1);
if (i >= m - 1 && zeros == 26) result.push_back(i - m + 1);
}
return result;
}
};function findAnagrams(s, p) {
const n = s.length, m = p.length;
const result = [];
if (m > n) return result;
const diff = new Array(26).fill(0);
for (let i = 0; i < m; i++) diff[p.charCodeAt(i) - 97]--;
let zeros = 0;
for (let c = 0; c < 26; c++) if (diff[c] === 0) zeros++;
const add = (c, d) => {
if (diff[c] === 0) zeros--;
diff[c] += d;
if (diff[c] === 0) zeros++;
};
for (let i = 0; i < n; i++) {
add(s.charCodeAt(i) - 97, 1);
if (i >= m) add(s.charCodeAt(i - m) - 97, -1);
if (i >= m - 1 && zeros === 26) result.push(i - m + 1);
}
return result;
}Edge cases to test
plonger thans: the answer is emptypandsof the same length- Overlapping matches, such as in a string made of one repeated letter
- Windows that contain the right letters but with wrong counts (for example
aabagainstabb)
Hints
Hint 1
Every anagram of p has length p.length, so only windows of exactly that length need checking.
Hint 2
Two strings are anagrams when their 26 letter counts are equal.
Hint 3
When the window slides one step, only two counts change: the letter that enters and the letter that leaves. Keep the counts up to date instead of recounting.
FAQ
What is the best time complexity for Find All Anagrams in a String?
Optimal (fixed sliding window with a match counter) runs in O(n + m) time and O(1) extra space. p is counted once and every index of s enters and leaves the window once.
Which pattern does Find All Anagrams in a String use?
It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.
Is there a brute force solution for Find All Anagrams in a String?
Yes. Brute force (recount every window) takes O(n · m) time and O(1) space. Count the letters of p once.
Which edge cases should I test for Find All Anagrams in a String?
p longer than s: the answer is empty; p and s of the same length; Overlapping matches, such as in a string made of one repeated letter; Windows that contain the right letters but with wrong counts (for example aab against abb).