#438
Find All Anagrams in a String
Medium Fixed window + counts
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return every starting index in s where a rearrangement of p begins.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: every start index where a rearrangement of p begins in s.
Why this works: same counting window as above, but record every match.
Example: s = "cbaebabacd", p = "abc"
index 0 "cba" ✓index 6 "bac" ✓answer [0, 6]
✦Hints open one at a time
Same as Permutation in String, but collect every match instead of stopping.
Compare two 26-length count arrays — that's O(26) per step, which is fine.
↗Approach
Build counts of p. Slide a window of length |p| over s, updating window counts by adding the new character and removing the old one. Whenever the arrays are equal, record the window start.
</>Solution (Java)
import java.util.*;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int n = p.length();
if (n > s.length()) return res;
int[] need = new int[26], window = new int[26];
for (int i = 0; i < n; i++) {
need[p.charAt(i) - 'a']++;
window[s.charAt(i) - 'a']++;
}
if (Arrays.equals(need, window)) res.add(0);
for (int i = n; i < s.length(); i++) {
window[s.charAt(i) - 'a']++;
window[s.charAt(i - n) - 'a']--;
if (Arrays.equals(need, window)) res.add(i - n + 1); // window start
}
return res;
}
}!Common mistake
Recording the end index of the window instead of the start.
Complexity
- Time: O(26 · n).
- Space: O(26).
Topic: Sliding Window
🎬 Episode 10: video coming soon