LeetCode 438: Find All Anagrams in a String (Fixed-Size Sliding Window)
LeetCode 438StringSliding WindowInterviewToday we solve LeetCode 438 - Find All Anagrams in a String.
Source: https://leetcode.com/problems/find-all-anagrams-in-a-string/
English
Problem Summary
Given two strings s and p, return all start indices in s where the substring is an anagram of p. Order of output indices should be ascending.
Key Insight
Anagrams have exactly the same character counts. So we keep a fixed-size sliding window of length len(p) on s, and compare frequency arrays of 26 lowercase letters.
Brute Force and Limitations
Brute force checks every substring of length m and sorts it (or recounts from scratch), leading to O(n * m log m) or O(n * m). This is unnecessary repeated work.
Optimal Algorithm Steps
1) Build frequency array need for p.
2) Move right pointer through s, updating window.
3) Once window size exceeds m, remove the left char.
4) When size equals m, compare arrays; if equal, record left index.
Complexity Analysis
Time: O(26 * n) (array comparison has constant 26 length), effectively O(n).
Space: O(1) extra (two 26-length arrays).
Common Pitfalls
- Forgetting to shrink window back to length m.
- Updating left pointer without decrementing outgoing char count.
- Using hash maps when only lowercase letters are involved (unnecessary overhead).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
int n = s.length(), m = p.length();
if (n < m) return ans;
int[] need = new int[26];
int[] win = new int[26];
for (char c : p.toCharArray()) need[c - 'a']++;
int left = 0;
for (int right = 0; right < n; right++) {
win[s.charAt(right) - 'a']++;
if (right - left + 1 > m) {
win[s.charAt(left) - 'a']--;
left++;
}
if (right - left + 1 == m && Arrays.equals(need, win)) {
ans.add(left);
}
}
return ans;
}
}func findAnagrams(s string, p string) []int {
n, m := len(s), len(p)
ans := []int{}
if n < m {
return ans
}
need := [26]int{}
win := [26]int{}
for i := 0; i < m; i++ {
need[p[i]-'a']++
}
left := 0
for right := 0; right < n; right++ {
win[s[right]-'a']++
if right-left+1 > m {
win[s[left]-'a']--
left++
}
if right-left+1 == m && need == win {
ans = append(ans, left)
}
}
return ans
}class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int n = (int)s.size(), m = (int)p.size();
if (n < m) return ans;
array<int,26> need{}, win{};
for (char c : p) need[c - 'a']++;
int left = 0;
for (int right = 0; right < n; ++right) {
win[s[right] - 'a']++;
if (right - left + 1 > m) {
win[s[left] - 'a']--;
left++;
}
if (right - left + 1 == m && need == win) {
ans.push_back(left);
}
}
return ans;
}
};from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(s), len(p)
if n < m:
return []
need = [0] * 26
win = [0] * 26
for ch in p:
need[ord(ch) - ord('a')] += 1
ans = []
left = 0
for right, ch in enumerate(s):
win[ord(ch) - ord('a')] += 1
if right - left + 1 > m:
win[ord(s[left]) - ord('a')] -= 1
left += 1
if right - left + 1 == m and win == need:
ans.append(left)
return ansvar findAnagrams = function(s, p) {
const n = s.length, m = p.length;
const ans = [];
if (n < m) return ans;
const need = new Array(26).fill(0);
const win = new Array(26).fill(0);
for (const ch of p) need[ch.charCodeAt(0) - 97]++;
let left = 0;
for (let right = 0; right < n; right++) {
win[s.charCodeAt(right) - 97]++;
if (right - left + 1 > m) {
win[s.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === m) {
let ok = true;
for (let i = 0; i < 26; i++) {
if (need[i] !== win[i]) { ok = false; break; }
}
if (ok) ans.push(left);
}
}
return ans;
};中文
题目概述
给定字符串 s 和 p，请找出 s 中所有是 p 的字母异位词的子串起始下标，并按升序返回。
核心思路
异位词的本质是“字符频次完全相同”。因此我们在 s 上维护一个长度固定为 len(p) 的滑动窗口，比较窗口频次数组和 p 频次数组即可。
暴力解法与不足
暴力法对每个长度为 m 的子串做排序或重建计数，复杂度大约是 O(n*m\log m) 或 O(n*m)，重复计算很多。
最优算法步骤
1）先统计 p 的频次数组 need。
2）右指针扩展窗口并更新 win。
3）若窗口长度超过 m，移动左指针并扣减移出字符计数。
4）当窗口长度等于 m 时比较频次数组；相同则记录当前左边界。
复杂度分析
时间复杂度：O(26*n)，常数 26 固定，可视为 O(n)。
空间复杂度：O(1)，仅使用两个长度为 26 的数组。
常见陷阱
- 忘记把窗口收缩回固定长度 m。
- 左指针前移时漏掉对移出字符的计数减一。
- 明明是 26 个小写字母却用哈希表，代码更慢更复杂。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
int n = s.length(), m = p.length();
if (n < m) return ans;
int[] need = new int[26];
int[] win = new int[26];
for (char c : p.toCharArray()) need[c - 'a']++;
int left = 0;
for (int right = 0; right < n; right++) {
win[s.charAt(right) - 'a']++;
if (right - left + 1 > m) {
win[s.charAt(left) - 'a']--;
left++;
}
if (right - left + 1 == m && Arrays.equals(need, win)) {
ans.add(left);
}
}
return ans;
}
}func findAnagrams(s string, p string) []int {
n, m := len(s), len(p)
ans := []int{}
if n < m {
return ans
}
need := [26]int{}
win := [26]int{}
for i := 0; i < m; i++ {
need[p[i]-'a']++
}
left := 0
for right := 0; right < n; right++ {
win[s[right]-'a']++
if right-left+1 > m {
win[s[left]-'a']--
left++
}
if right-left+1 == m && need == win {
ans = append(ans, left)
}
}
return ans
}class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int n = (int)s.size(), m = (int)p.size();
if (n < m) return ans;
array<int,26> need{}, win{};
for (char c : p) need[c - 'a']++;
int left = 0;
for (int right = 0; right < n; ++right) {
win[s[right] - 'a']++;
if (right - left + 1 > m) {
win[s[left] - 'a']--;
left++;
}
if (right - left + 1 == m && need == win) {
ans.push_back(left);
}
}
return ans;
}
};from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(s), len(p)
if n < m:
return []
need = [0] * 26
win = [0] * 26
for ch in p:
need[ord(ch) - ord('a')] += 1
ans = []
left = 0
for right, ch in enumerate(s):
win[ord(ch) - ord('a')] += 1
if right - left + 1 > m:
win[ord(s[left]) - ord('a')] -= 1
left += 1
if right - left + 1 == m and win == need:
ans.append(left)
return ansvar findAnagrams = function(s, p) {
const n = s.length, m = p.length;
const ans = [];
if (n < m) return ans;
const need = new Array(26).fill(0);
const win = new Array(26).fill(0);
for (const ch of p) need[ch.charCodeAt(0) - 97]++;
let left = 0;
for (let right = 0; right < n; right++) {
win[s.charCodeAt(right) - 97]++;
if (right - left + 1 > m) {
win[s.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === m) {
let ok = true;
for (let i = 0; i < 26; i++) {
if (need[i] !== win[i]) { ok = false; break; }
}
if (ok) ans.push(left);
}
}
return ans;
};
Comments