1.1 Sliding Window là gì?

Quan hệ với Two Pointers (Tuần 2)

Sliding Window là biến thể chuyên biệt của Two Pointers Same Direction. Khác biệt:

• Two Pointers Same Direction: hai pointer độc lập về logic, một đọc, một ghi (như Move Zeroes).
• Sliding Window: hai pointer cùng định nghĩa một cửa sổ liên tục; bài toán xét tính chất của cửa sổ đó.

Tinh thần

Brute force: thử mọi cặp (i, j) với i ≤ j → O(n²) cửa sổ. Sliding window: chỉ duyệt qua các cửa sổ "có ý nghĩa" theo đường monoton → O(n).

1.2 Hai biến thể — Trực quan

Cả hai biến thể đều có right tăng đơn điệu. Khác biệt: Fixed có left = right − k + 1; Variable có left tăng theo điều kiện.

1.3 Tín hiệu nhận biết Sliding Window

1.4 Vì sao Sliding Window luôn O(n)? Phân tích Amortised

Một lo lắng tự nhiên: trong Variable Window, vòng while shrink có thể chạy nhiều lần trong một bước — sao tổng time là O(n)?

Phân tích amortised

Quan sát: cả left và right đều di chuyển chỉ tiến.

• right đi từ 0 đến n−1 → tổng nhiều nhất n bước.
• left đi từ 0 đến n−1 → tổng nhiều nhất n bước.
• Mỗi bước có thể có nhiều shrink, nhưng tổng số shrink qua cả thuật toán ≤ n.

2.1 Template chuẩn — Fixed Window

def fixed_window(arr, k):
    # Pha 1: build cửa sổ đầu tiên
    window_state = init(arr[:k])
    best = evaluate(window_state)

    # Pha 2: trượt cửa sổ
    for i in range(k, len(arr)):
        window_state = add(window_state, arr[i])         # thêm bên phải
        window_state = remove(window_state, arr[i - k])  # bỏ bên trái
        best = update_best(best, evaluate(window_state))
    return best

Ba chỗ tuỳ biến

1. window_state: tổng / max / Counter / set / bitmask...
2. add, remove: cập nhật O(1) nếu state là tổng / Counter.
3. evaluate: tính giá trị muốn theo dõi từ state.

Time chuẩn: O(n) nếu add/remove/evaluate đều O(1) hoặc O(k) phân bổ.

2.2 Worked Example 1 — Maximum Average Subarray I

Đề (LeetCode #643): Mảng nums, số k. Tìm trung bình lớn nhất của subarray liên tiếp size k.

Constraints: 1 ≤ k ≤ n ≤ 10⁵ → cần O(n).

Brute force

Duyệt mọi cửa sổ, tính tổng → O(n × k). Với n,k = 10⁵ → 10¹⁰ → TLE.

Sliding Window

def findMaxAverage(nums, k):
    window_sum = sum(nums[:k])           # cửa sổ đầu tiên
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]   # add right, remove left — O(1)
        best = max(best, window_sum)
    return best / k

Time O(n), Space O(1).

2.3 Maximum Average — Trace tay

nums = [1, 12, -5, -6, 50, 3], k = 4.

Cửa sổ ban đầu

nums[0..3] = [1,12,-5,-6], sum = 2, best = 2.

Trả về 51 / 4 = 12.75.

2.4 Worked Example 2 — Find All Anagrams in a String

Đề (LeetCode #438): String s, pattern p. Tìm mọi index bắt đầu của substring trong s là anagram của p.

Ví dụ: s = "cbaebabacd", p = "abc" → [0, 6] (substring "cba" và "bac").

Ý tưởng

Cửa sổ size len(p). So sánh Counter của cửa sổ với Counter của p.

from collections import Counter
def findAnagrams(s, p):
    if len(s) < len(p): return []
    k = len(p)
    p_cnt = Counter(p)
    w_cnt = Counter(s[:k])
    res = []
    if w_cnt == p_cnt: res.append(0)
    for i in range(k, len(s)):
        w_cnt[s[i]] += 1                        # add
        w_cnt[s[i - k]] -= 1                    # remove
        if w_cnt[s[i - k]] == 0:
            del w_cnt[s[i - k]]
        if w_cnt == p_cnt: res.append(i - k + 1)
    return res

2.5 Find Anagrams — Tối ưu so sánh O(1)

Code 2.4 vẫn đúng nhưng w_cnt == p_cnt tốn O(k) mỗi bước → O(n × k). Có thể tối ưu O(n).

Đếm số "match"

Duy trì biến matches = số ký tự có w_cnt[ch] == p_cnt[ch]. Anagram tương đương matches == số ký tự khác nhau trong p_cnt.

def findAnagrams(s, p):
    if len(s) < len(p): return []
    p_cnt = Counter(p)
    w_cnt = Counter()
    matches = 0
    needed = len(p_cnt)
    res = []
    for i, ch in enumerate(s):
        # add
        w_cnt[ch] += 1
        if w_cnt[ch] == p_cnt[ch]: matches += 1
        elif w_cnt[ch] == p_cnt[ch] + 1: matches -= 1
        # remove (khi cửa sổ vượt size)
        if i >= len(p):
            left_ch = s[i - len(p)]
            if w_cnt[left_ch] == p_cnt[left_ch]: matches -= 1
            elif w_cnt[left_ch] == p_cnt[left_ch] + 1: matches += 1
            w_cnt[left_ch] -= 1
        if matches == needed:
            res.append(i - len(p) + 1)
    return res

Time O(n), Space O(k).

2.6 Worked Example 3 — Permutation in String

Đề (LeetCode #567): Cho s1, s2. Trả True nếu s2 chứa một permutation của s1 dưới dạng substring.

Đây chính là Find Anagrams nhưng chỉ cần biết "có hay không" thay vì liệt kê.

def checkInclusion(s1, s2):
    if len(s1) > len(s2): return False
    p_cnt = Counter(s1)
    w_cnt = Counter(s2[:len(s1)])
    if w_cnt == p_cnt: return True
    for i in range(len(s1), len(s2)):
        w_cnt[s2[i]] += 1
        w_cnt[s2[i - len(s1)]] -= 1
        if w_cnt[s2[i - len(s1)]] == 0:
            del w_cnt[s2[i - len(s1)]]
        if w_cnt == p_cnt: return True
    return False

2.7 Worked Example 4 — Maximum Number of Vowels in a Substring

Đề (LeetCode #1456): String s, số k. Tìm số nguyên âm nhiều nhất trong substring size k.

def maxVowels(s, k):
    vowels = set('aeiou')
    count = sum(1 for ch in s[:k] if ch in vowels)
    best = count
    for i in range(k, len(s)):
        if s[i] in vowels: count += 1
        if s[i - k] in vowels: count -= 1
        best = max(best, count)
    return best

Time O(n), Space O(1).

Mẫu chung của Fixed Window đếm

Nhìn lại WE1, WE4: cùng cấu trúc — state = count/sum, update bằng +/−. Đây là cấu trúc đơn giản nhất của Fixed Window và xuất hiện ở rất nhiều bài.

Knowledge Check — Fixed Window

3.1 Template chuẩn — Variable Window

def variable_window(arr):
    state = init()
    left = 0
    best = init_best()
    for right in range(len(arr)):
        state = add(state, arr[right])
        # Shrink: di chuyển left cho đến khi cửa sổ "hợp lệ"
        while not is_valid(state):
            state = remove(state, arr[left])
            left += 1
        best = update_best(best, right - left + 1)
    return best

Ba điểm tuỳ biến

1. state: cấu trúc theo dõi cửa sổ (Counter, sum, max...).
2. is_valid: điều kiện bài toán — quyết định khi nào shrink.
3. best: max length / min length / count.

3.2 Shrink Condition — Trái tim của Variable Window

Câu hỏi quan trọng nhất khi thiết kế Variable Window: khi nào shrink?

Hai mẫu shrink phổ biến

1. "While vi phạm, shrink để khôi phục hợp lệ" — bài tìm max length thoả điều kiện.
2. "While đã thoả, shrink để tìm min" — bài tìm min length thoả điều kiện.

3.3 Worked Example 5 — Minimum Size Subarray Sum

Đề (LeetCode #209): Mảng nums dương, số target. Tìm độ dài subarray ngắn nhất có tổng ≥ target. Trả 0 nếu không có.

Pattern: "Shrink khi đã thoả"

def minSubArrayLen(target, nums):
    left = 0
    cur_sum = 0
    best = float('inf')
    for right in range(len(nums)):
        cur_sum += nums[right]
        while cur_sum >= target:                # đã thoả → cố thu nhỏ
            best = min(best, right - left + 1)
            cur_sum -= nums[left]
            left += 1
    return best if best != float('inf') else 0

Time O(n), Space O(1).

Vì sao bài này yêu cầu nums dương?

Nếu có số âm, mở rộng right không nhất thiết tăng tổng → không monoton → sliding window không áp dụng được. Bài có số âm cần Prefix Sum + Deque (Tuần 6).

3.4 Min Size Subarray — Trace tay

target = 7, nums = [2, 3, 1, 2, 4, 3]. Kỳ vọng: 2 (subarray [4,3]).

Kết quả: 2.

3.5 Worked Example 6 — Longest Substring Without Repeating (Set version)

Đề (LeetCode #3): String s. Độ dài substring dài nhất không có ký tự lặp.

Variant 1 — Set + while shrink

def lengthOfLongestSubstring(s):
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:                  # shrink cho đến khi hợp lệ
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

Time O(n), Space O(k) với k = số ký tự khác nhau.

Đây là pattern "Shrink khi vi phạm"

Cửa sổ phải không có ký tự lặp. Khi ch đã có trong set, vi phạm — shrink left cho đến khi ch không còn trong set.

3.6 Longest Substring No Repeat — Variant 2 (Last-seen index)

Variant 1 chạy đúng O(n) amortised nhưng có thể tối ưu hằng số bằng "nhảy left" thay vì shrink từng bước:

def lengthOfLongestSubstring(s):
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1       # nhảy left thẳng tới sau vị trí cũ
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

So sánh

3.7 Worked Example 7 — Longest Substring with At Most K Distinct Characters

Đề (LeetCode #340): String s, số k. Độ dài substring dài nhất có tối đa k loại ký tự khác nhau.

Pattern: "Shrink khi vi phạm" với Counter

from collections import defaultdict
def lengthOfLongestSubstringKDistinct(s, k):
    cnt = defaultdict(int)
    left = 0
    best = 0
    for right, ch in enumerate(s):
        cnt[ch] += 1
        while len(cnt) > k:                # vi phạm
            cnt[s[left]] -= 1
            if cnt[s[left]] == 0:
                del cnt[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

Time O(n), Space O(k).

3.8 Longest Substring K Distinct — Trace

s = "eceba", k = 2. Kỳ vọng: 3 (substring "ece").

Kết quả: 3.

3.9 Worked Example 8 — Fruit Into Baskets

Đề (LeetCode #904): Mảng fruits. Hai giỏ, mỗi giỏ một loại. Bắt đầu từ một vị trí bất kỳ, hái liên tiếp. Tối đa hái được bao nhiêu trái?

Đây chính là Longest Substring with At Most K Distinct với k = 2.

def totalFruit(fruits):
    cnt = defaultdict(int)
    left = 0
    best = 0
    for right, f in enumerate(fruits):
        cnt[f] += 1
        while len(cnt) > 2:
            cnt[fruits[left]] -= 1
            if cnt[fruits[left]] == 0:
                del cnt[fruits[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

3.10 Worked Example 9 — Longest Repeating Character Replacement

Đề (LeetCode #424): String s chữ hoa, số k. Có thể đổi tối đa k ký tự để được substring toàn cùng một ký tự. Độ dài lớn nhất là bao nhiêu?

Quan sát then chốt

Window hợp lệ ⟺ (window_length − max_freq_in_window) ≤ k. Tức số ký tự "khác đa số" trong window không vượt k.

from collections import defaultdict
def characterReplacement(s, k):
    cnt = defaultdict(int)
    left = 0
    max_freq = 0
    best = 0
    for right, ch in enumerate(s):
        cnt[ch] += 1
        max_freq = max(max_freq, cnt[ch])
        # vi phạm: cần đổi nhiều hơn k ký tự
        if (right - left + 1) - max_freq > k:
            cnt[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Time O(n), Space O(26).

3.11 Worked Example 10 — Minimum Window Substring (Hard)

Đề (LeetCode #76): String s, t. Tìm substring ngắn nhất của s chứa mọi ký tự của t (kể cả tần suất).

Ví dụ: s = "ADOBECODEBANC", t = "ABC" → "BANC".

Pattern: "Shrink khi đã thoả" + Counter + matches

from collections import Counter
def minWindow(s, t):
    if not t or len(s) < len(t): return ""
    need = Counter(t)
    have = defaultdict(int)
    needed = len(need)
    formed = 0
    left = 0
    best_len = float('inf')
    best_l, best_r = 0, 0
    for right, ch in enumerate(s):
        have[ch] += 1
        if ch in need and have[ch] == need[ch]:
            formed += 1
        while formed == needed:           # đã thoả → shrink để tìm min
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_l, best_r = left, right
            have[s[left]] -= 1
            if s[left] in need and have[s[left]] < need[s[left]]:
                formed -= 1
            left += 1
    return s[best_l:best_r+1] if best_len != float('inf') else ""

3.12 Min Window — Phân tích chi tiết

Vai trò các biến

• need = Counter của t (yêu cầu).
• have = Counter của window hiện tại.
• needed = số ký tự khác nhau trong t.
• formed = số ký tự khác nhau đã đủ tần suất trong window.

Logic cập nhật formed

Tăng khi have[ch] == need[ch] (vừa đủ — không tăng nếu vượt). Giảm khi shrink làm have[s[left]] < need[s[left]] (vừa thiếu).

Vì sao cần biến formed mà không so sánh trực tiếp have == need?

So sánh hai dict tốn O(số ký tự khác nhau) mỗi bước → tổng O(nk). Biến formed cập nhật O(1) → tổng O(n). Giống tinh thần matches ở Find All Anagrams (2.5).

3.13 Min Window — Trace tay

s = "ADOBECODEBANC", t = "ABC". need={A:1,B:1,C:1}, needed=3.

Kết quả: "BANC". Đầy đủ 13 bước có trong code repository — đây chỉ là tóm tắt.

Knowledge Check — Variable Window

4.1 Decision Tree — Fixed vs Variable

Mẫu nhận diện trong đề

• "size k", "length k" → Fixed.
• "longest", "shortest" + điều kiện → Variable.
• "đếm subarray thoả X" → Variable + kỹ thuật countAtMost(K) − countAtMost(K−1).

4.2 Common Pitfalls

1. Quên xoá key khỏi Counter khi count về 0.

   cnt[s[left]] -= 1
   if cnt[s[left]] == 0: del cnt[s[left]]      # ĐỪNG QUÊN

   Nếu không xoá, len(cnt) sai → bài K Distinct sẽ TLE hoặc kết quả sai.
2. Sai vị trí cập nhật best trong Variable Window. Cập nhật trong/sau vòng while tuỳ bài: max length thì sau (để window đã hợp lệ); min length thì trong while (để bắt được window vừa thoả).
3. Hiểu sai amortised vs worst-case. Một số sinh viên thấy while trong for nghĩ là O(n²). Phải lập luận: "left chỉ tăng — tổng số bước while ≤ n".
4. Áp dụng Sliding Window cho mảng có số âm. Sliding Window cần monoton. Số âm phá monoton trong nhiều bài — phải kiểm tra trước khi áp dụng.
5. Quên trường hợp window rỗng / cửa sổ ban đầu. Min Subarray Sum: nếu không tồn tại → trả 0 chứ không phải float('inf'). Min Window Substring: trả "" nếu không tìm thấy.

Tổng kết Tuần 4

Đã học

• Sliding Window: biến thể chuyên biệt của Two Pointers Same Direction.
• Fixed Window: incremental update O(1) — sum, count, Counter với mẹo "matches".
• Variable Window: shrink condition là trái tim — "vi phạm" cho max length, "đã thoả" cho min length.
• Phân tích amortised: tổng số lần left/right di chuyển ≤ 2n → O(n).
• Kết hợp với Hash: Counter làm window state cho hầu hết bài substring.
• Bẫy: xoá key khi count=0, monoton vs số âm, vị trí update best.

Bài về nhà (12 bài)

1. LeetCode #643 — Maximum Average Subarray I
2. LeetCode #1456 — Maximum Number of Vowels in a Substring of Given Length
3. LeetCode #438 — Find All Anagrams in a String
4. LeetCode #567 — Permutation in String
5. LeetCode #209 — Minimum Size Subarray Sum
6. LeetCode #3 — Longest Substring Without Repeating Characters (cả 2 variant)
7. LeetCode #340 — Longest Substring with At Most K Distinct Characters
8. LeetCode #904 — Fruit Into Baskets
9. LeetCode #424 — Longest Repeating Character Replacement
10. LeetCode #76 — Minimum Window Substring (Hard — bài boss của tuần)
11. LeetCode #1004 — Max Consecutive Ones III
12. LeetCode #2962 — Count Subarrays Where Max Element Appears at Least K Times