Step 1: Use fixed-length sliding window
"Every anagram of p has length len(p), so I slide a fixed-size window across s."
Step 2: Compare frequencies
"A window is valid if its character frequency exactly matches p's frequency."
Example:
s = "cbaebabacd", p = "abc"
window size = 3
"cba" -> anagram, index 0
"bae" -> no
"aeb" -> no
...
"bac" -> anagram, index 6
answer = [0, 6]
Step 3: Complexity
"Time is O(n) and space is O(1)."
Possible follow-ups
- Why not sort each window? "Sorting would cost more; counts update in constant time."
中文：固定長度窗口加上字母頻率比較，是這題的核心。
Step 1: Point out the key observation
"An anagram has the same character frequencies as the original string, just in different order. So instead of generating all permutations, we just need to find windows in s of length len(p) that have identical character frequencies."
Step 2: Explain why sliding window fits
"Since we're looking for substrings of a fixed length, this is a natural fit for a fixed-size sliding window. We slide one character at a time -- adding the new right character and removing the old left character."
s = "cbaebacd", p = "abc"
window size = 3
[c b a] e b a c d -> match
[b a e] b a c d
[a e b] a c d
[e b a] c d
[b a c] d -> match
[a c d]
Step 3: Explain the matches counter
"Naively comparing two 26-element frequency arrays at every step costs O(26) per slide. Instead, we maintain a matches counter -- how many of the 26 characters currently have equal frequency in both arrays. When matches hits 26, we found an anagram."
need = {a:1, b:1, c:1, others:0}
window = {a:1, b:1, c:1, others:0}
matches = 26 -> anagram
Step 4: Explain how to update matches
"The key is updating matches correctly. Before changing window, check if it currently equals need; if so, decrement matches because we're about to break that equality. After changing, check again; if they're equal now, increment matches."
# Add the right character.
if window[add] == need[add]: matches -= 1
window[add] += 1
if window[add] == need[add]: matches += 1
# Remove the left character; same logic.
if window[remove] == need[remove]: matches -= 1
window[remove] -= 1
if window[remove] == need[remove]: matches += 1
Step 5: Walk through a complete example
s = "cbaebacd", p = "abc"
need = {a:1, b:1, c:1, others:0}
initial window = {c:1, b:1, a:1}
matches = 26 -> result = [0]
right=3, left=0: add e, remove c
add e: 0 -> 1, need[e] = 0, no longer equal -> matches = 25
remove c: 1 -> 0, need[c] = 1, no longer equal -> matches = 24
right=4, left=1: add b, remove b
add b: 1 -> 2, need[b] = 1, breaks equality -> matches = 23
remove b: 2 -> 1, need[b] = 1, equal again -> matches = 24
right=5, left=2: add a, remove a
add a: 1 -> 2, need[a] = 1, breaks equality -> matches = 23
remove a: 2 -> 1, need[a] = 1, equal again -> matches = 24
right=6, left=3: add c, remove e
add c: 0 -> 1, need[c] = 1, equal again -> matches = 25
remove e: 1 -> 0, need[e] = 0, equal again -> matches = 26
result = [0, 4]
return [0, 4]
Step 6: Complexity
"Time is O(n) because each character is added and removed exactly once, and each window update is O(1) thanks to the matches counter. Space is O(1) because we only use two fixed-size arrays of 26."
Possible follow-ups
- Why use an array of size 26 instead of a Counter? "Both work, but a fixed array gives O(1) index access and makes the
matches optimization more natural."
- What if the string contains characters outside lowercase letters? "We would switch to a hash map and track how many required characters are fully satisfied instead of assuming exactly 26 buckets."
中文：開場點出 anagram 等於頻率相同，說明 fixed-size sliding window，重點解釋 matches counter 的更新邏輯，並走完整例子展示每步變化。