Find All Anagrams in a String — Problem & Solution
Find All Anagrams in a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find All Anagrams in a String is a medium coding problem on strings, hash table and sliding window, asked in Databricks interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Databricks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two strings s and p, return an array of all the start indices of p's anagrams in s, in increasing order.
Example 1
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation: Substrings "cba" (index 0) and "bac" (index 6).
Example 2
Input: s = "abab", p = "ab"
Output: [0,1,2]
Constraints
1 <= s.length, p.length <= 40s and p consist of lowercase English letters.
Hints for Find All Anagrams in a String
Hint 1
Compare letter-frequency counts of a sliding window of length |p| against p's counts.
Hint 2
Update the window counts incrementally: add the entering char, remove the leaving one.
How to solve Find All Anagrams in a String
An anagram of p is any window of s with the same length and the same character frequencies. So slide a fixed-width window of size |p| across s, updating counts incrementally, and record every position where the tables agree.
Approach
- Build a frequency table for
p. - Slide a window of width
|p|acrosss, adding the entering character's count. - Once the window is wider than
|p|, subtract the character leaving on the left. - When the window reaches full width, compare the two tables and record the start index on a match.
- Return the indices in the order found, which is already increasing.
Why it works
Two equal-length strings are anagrams exactly when their character multisets match, and a fixed-size count table is that multiset. Updating incrementally — one addition and one removal per step — is what keeps the sweep linear instead of rebuilding a table for every window. Because the window advances left to right, the recorded indices come out sorted with no extra work.
Complexity
- Time —
O(|s| · alphabet) - Space —
O(1)
Pitfalls
- The window is fixed width; growing and shrinking it solves a different problem.
- Remove the outgoing character as well as adding the incoming one.
- Start recording only once the window is exactly
|p|wide. - If
pis longer thansthe answer is empty, which falls out because the window never fills.
Reference solution
Python
from typing import List
def findAnagrams(s: str, p: str) -> List[int]:
out = []
if len(p) > len(s):
return out
need = [0] * 26
have = [0] * 26
for ch in p:
need[ord(ch) - 97] += 1
for i, ch in enumerate(s):
have[ord(ch) - 97] += 1
if i >= len(p):
have[ord(s[i - len(p)]) - 97] -= 1
if i >= len(p) - 1 and have == need:
out.append(i - len(p) + 1)
return outJava
public static int[] findAnagrams(String s, String p) {
List<Integer> out = new ArrayList<>();
int n = s.length(), m = p.length();
if (m <= n) {
int[] need = new int[26];
int[] have = new int[26];
for (int i = 0; i < m; i++) need[p.charAt(i) - 'a']++;
for (int i = 0; i < n; i++) {
have[s.charAt(i) - 'a']++;
if (i >= m) have[s.charAt(i - m) - 'a']--;
if (i >= m - 1 && Arrays.equals(need, have)) out.add(i - m + 1);
}
}
int[] res = new int[out.size()];
for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
return res;
}C++
vector<int> findAnagrams(string s, string p) {
vector<int> out;
int n = (int) s.size(), m = (int) p.size();
if (m > n) return out;
vector<int> need(26, 0), have(26, 0);
for (int i = 0; i < m; i++) need[p[i] - 'a']++;
for (int i = 0; i < n; i++) {
have[s[i] - 'a']++;
if (i >= m) have[s[i - m] - 'a']--;
if (i >= m - 1 && need == have) out.push_back(i - m + 1);
}
return out;
}JavaScript
var findAnagrams = function(s, p) {
const out = [];
if (p.length > s.length) return out;
const need = new Array(26).fill(0);
const have = new Array(26).fill(0);
for (const ch of p) need[ch.charCodeAt(0) - 97]++;
for (let i = 0; i < s.length; i++) {
have[s.charCodeAt(i) - 97]++;
if (i >= p.length) have[s.charCodeAt(i - p.length) - 97]--;
if (i >= p.length - 1) {
let ok = true;
for (let j = 0; j < 26; j++) {
if (need[j] !== have[j]) { ok = false; break; }
}
if (ok) out.push(i - p.length + 1);
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets