Chương 27 - Sliding Window

Sliding Window = two pointers cùng chiều. Window [l, r] mở rộng r, co l khi vi phạm điều kiện. Pattern này giải gọn rất nhiều bài “longest / shortest / count substring/subarray thoả điều kiện” trong O(n).

Mục tiêu chương

Sau chương này, bạn sẽ:

• Variable-size window khi predicate monotonic dưới expand/shrink.
• Fixed-size window: duy trì r - l + 1 == k.
• Exactly K = atMost(K) − atMost(K−1) - pattern tiêu biểu của sliding window.
• Tránh re-compute trong window bằng cách track state incremental.

Khi nào dùng pattern này?

• Bài: “longest / shortest / count subarray có tổng / điều kiện X”.
• Mảng / chuỗi với giá trị chỉ thêm phần tử mới, không có random access.
• Đặc biệt khi bài có monotonic predicate trên window length:
  • “Tổng ≤ S, max length” → window expand khi nhỏ, contract khi lớn.
  • “Có exactly K distinct” → trick = atMostK - atMost(K-1).

2 mẫu chính:

Mẫu	Pseudo
Fixed-size window	duy trì r - l + 1 == k luôn
Variable-size window	mở rộng r luôn, co l đến khi valid() thoả

Template code

from collections import defaultdict, Counter

# 1) Variable-size: longest with condition
l = 0
state = ...
best = 0
for r in range(len(s)):
    add(s[r], state)
    while not valid(state):
        remove(s[l], state)
        l += 1
    best = max(best, r - l + 1)


# 2) Count subarray "exactly K" = "at most K" - "at most K-1"
def at_most(k):
    l, total = 0, 0
    state = ...
    for r in range(len(arr)):
        add(arr[r], state)
        while violates(state):
            remove(arr[l], state)
            l += 1
        total += r - l + 1
    return total

result = at_most(k) - at_most(k - 1)

Bài tự luyện cuối chương

• LC 209 - Minimum Size Subarray Sum
• LC 340 - Longest Substring with At Most K Distinct
• LC 487 - Max Consecutive Ones II
• LC 904 - Fruit Into Baskets
• LC 1004 - Max Consecutive Ones III
• LC 1208 - Get Equal Substrings Within Budget

---

27.1 Longest Substring Without Repeating Characters (LC 3)

Đề bài

Cho chuỗi s. Tìm độ dài substring dài nhất không có ký tự lặp.

Ví dụ

Input:  s = "abcabcbb"      → Output: 3   (substring đẹp nhất: "abc")
Input:  s = "bbbbb"         → Output: 1   (substring "b")
Input:  s = "pwwkew"        → Output: 3   (substring "wke")

Ràng buộc

• 0 <= len(s) <= 5·10^4
• s chứa chữ, số, symbol, space

Clarifying questions

• Chuỗi rỗng? → Trả 0.
• Unicode? → Mặc định ASCII; dict đếm tổng quát.

Hướng tiếp cận

Sliding window + set / dict.

Mở rộng r. Khi s[r] đã trong window, co l cho đến khi không còn.

Tối ưu hơn - dict last-seen index: l = max(l, last_seen[s[r]] + 1).

Code Python 3

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last: dict[str, int] = {}
        l = 0
        best = 0
        for r, ch in enumerate(s):
            if ch in last and last[ch] >= l:
                l = last[ch] + 1
            last[ch] = r
            best = max(best, r - l + 1)
        return best

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(k) với k = bảng chữ.

Bình luận

• Bẫy last[ch] >= l: chỉ jump l khi last[ch] còn trong window.

Bài tự luyện liên quan

• LC 159 - Longest Substring with At Most Two Distinct Characters.
• LC 340 - At Most K Distinct.

---

27.2 Minimum Window Substring (LC 76)

Đề bài

Cho s, t. Tìm substring nhỏ nhất của s chứa mọi ký tự của t (kể cả frequency).

Ví dụ

Input:  s = "ADOBECODEBANC", t = "ABC"   → "BANC"

Ràng buộc

• m == len(s), n == len(t)
• 1 <= m, n <= 10^5

Clarifying questions

• t > s độ dài? → Trả ““.
• t có duplicate? → Có; phải đếm freq.

Hướng tiếp cận

Sliding window + 2 Counter.

• need = Counter(t). have đếm trong window.
• Khi have thoả mọi key >= need[key] → window valid → cố co l.
• Track (best_len, l_best, r_best).

Optimization: track formed (số key thoả) thay vì so sánh dict.

Code Python 3

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or len(t) > len(s):
            return ""
        need = Counter(t)
        have: dict[str, int] = {}
        required = len(need)
        formed = 0
        l = 0
        best = (float('inf'), 0, 0)
        for r, ch in enumerate(s):
            have[ch] = have.get(ch, 0) + 1
            if ch in need and have[ch] == need[ch]:
                formed += 1
            while formed == required:
                if r - l + 1 < best[0]:
                    best = (r - l + 1, l, r)
                have[s[l]] -= 1
                if s[l] in need and have[s[l]] < need[s[l]]:
                    formed -= 1
                l += 1
        return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

Phân tích độ phức tạp

• Thời gian: O(n + m). Bộ nhớ: O(k).

Bình luận

• formed là counter “đếm số key đã thoả”
  • formed == required là điều kiện valid.
• Bẫy: so sánh have == need mỗi vòng → O(k) mỗi bước → O(nk) tổng.

Bài tự luyện liên quan

• LC 567 - Permutation in String.
• LC 438 - Find All Anagrams.

---

27.3 Longest Repeating Character Replacement (LC 424)

Đề bài

Cho s và k. Bạn có thể đổi tối đa k ký tự thành ký tự bất kỳ. Tìm độ dài substring dài nhất có tất cả ký tự giống nhau sau khi đổi.

Ví dụ

Input:  s = "ABAB", k = 2   → 4
Input:  s = "AABABBA", k = 1 → 4 ("AABA" hoặc "ABBA")

Ràng buộc

• 1 <= len(s) <= 10^5
• s chỉ chứa chữ in hoa
• 0 <= k <= len(s)

Clarifying questions

• k = 0? → Window phải toàn cùng ký tự.
• n = 1? → Trả 1.

Hướng tiếp cận

Insight: window valid ↔︎ window_len - max_freq <= k (số ký tự cần đổi ≤ k).

Mở rộng r, cập nhật max_freq. Nếu vi phạm → co l 1 bước.

Trick: max_freq không cần “decrease” khi co l - vì kết quả không giảm khi max_freq chỉ giữ giá trị cũ (window vẫn không lớn hơn).

Code Python 3

from collections import defaultdict

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count: dict[str, int] = defaultdict(int)
        l = 0
        max_freq = 0
        best = 0
        for r, ch in enumerate(s):
            count[ch] += 1
            max_freq = max(max_freq, count[ch])
            while (r - l + 1) - max_freq > k:
                count[s[l]] -= 1
                l += 1
            best = max(best, r - l + 1)
        return best

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(26).

Bình luận

• Cùng pattern với LC 1004 (Max Consecutive Ones III)
  • max_freq = 1s.

Bài tự luyện liên quan

• LC 1004 - Max Consecutive Ones III.

---

27.4 Permutation in String (LC 567)

Đề bài

Cho s1, s2. Kiểm tra s2 có chứa permutation của s1 không (= có substring nào trong s2 mà Counter == Counter(s1)).

Ví dụ

Input:  s1="ab", s2="eidbaooo"
Output: True
Giải thích: s2 chứa "ba" - permutation của "ab"

Ràng buộc

• 1 <= len(s1), len(s2) <= 10^4
• s1, s2 chỉ chứa chữ thường

Clarifying questions

• s1 > s2? → Trả False.
• s1, s2 ASCII only? → Mặc định: chỉ chữ thường.

Hướng tiếp cận

Fixed-size sliding window với độ dài len(s1). So sánh 2 array đếm 26 phần tử mỗi bước.

Code Python 3

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        need = [0] * 26
        have = [0] * 26
        for ch in s1:
            need[ord(ch) - 97] += 1
        for i, ch in enumerate(s2):
            have[ord(ch) - 97] += 1
            if i >= len(s1):
                have[ord(s2[i - len(s1)]) - 97] -= 1
            if have == need:
                return True
        return False

Phân tích độ phức tạp

• Thời gian: O(n · 26) = O(n). Bộ nhớ: O(26).

Bình luận

• have == need so 2 list 26 phần tử = O(26) constant.
• Bài tương tự LC 438 - Find All Anagrams: trả về tất cả vị trí thay vì True/False.

Bài tự luyện liên quan

• LC 438 - Find All Anagrams in a String.
• LC 30 - Substring with Concatenation of All Words.

---

27.5 Subarrays with K Different Integers (LC 992)

Đề bài

Cho nums và k. Đếm số subarray có đúng k ký tự phân biệt.

Ví dụ

Input:  nums = [1,2,1,2,3], k = 2   → 7
Input:  nums = [1,2,1,3,4], k = 3   → 3

Ràng buộc

• 1 <= len(nums) <= 2·10^4
• 1 <= nums[i], k <= len(nums)

Clarifying questions

• k > n? → Trả 0.
• Mảng toàn cùng số? → 1 distinct; check k.

Hướng tiếp cận

Trick: “exactly K” = “at most K” - “at most K - 1”.

at_most(k): sliding window đếm số subarray với ≤ k distinct integer.

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:

        def at_most(k: int) -> int:
            count: dict[int, int] = defaultdict(int)
            distinct = 0
            l = 0
            total = 0
            for r in range(len(nums)):
                if count[nums[r]] == 0:
                    distinct += 1
                count[nums[r]] += 1
                while distinct > k:
                    count[nums[l]] -= 1
                    if count[nums[l]] == 0:
                        distinct -= 1
                    l += 1
                total += r - l + 1
            return total

        return at_most(k) - at_most(k - 1)

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(k).

Bình luận

• Trick “exactly = atMost(k) − atMost(k−1)” là kỹ thuật tiêu biểu của sliding window: bài “exactly” khó hơn “at most”, nên luôn chuyển về dạng dễ.
• Pattern: LC 1248 (Count Nice Subarrays), LC 930 (Binary Subarrays With Sum).

Bài tự luyện liên quan

• LC 1248 - Count Number of Nice Subarrays.
• LC 930 - Binary Subarrays With Sum.

---

27.6 Sliding Window Maximum (LC 239) - recap

Đã giải đầy đủ ở Chương 18.4 (Monotonic Queue).

Code Python 3

from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq: deque[int] = deque()  # lưu **index**, value tại dq giảm dần
        result: List[int] = []
        for i, x in enumerate(nums):
            while dq and nums[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result

Liên hệ

• Là kết hợp của sliding window + monotonic deque.
• Monotonic deque chứa các index có value giảm dần - head luôn là max của window.
• 2 thao tác cốt lõi mỗi bước:
  1. Pop back mọi index có value ≤ giá trị mới (chúng không còn cơ hội làm max).
  2. Pop front nếu index đã ra ngoài window (dq[0] <= i - k).

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(k).

Bài tự luyện liên quan

• LC 1438 - Longest Continuous Subarray With Absolute Diff ≤ Limit.

Tóm tắt chương & Quyết định

Sliding window applicability

• Điều kiện cần: tồn tại invariant đơn điệu khi cửa sổ mở rộng / co lại.
  • Subarray sum không âm → mở rộng tăng tổng, co giảm tổng ✅.
  • Subarray sum có âm → mở rộng có thể giảm tổng ❌ (dùng prefix + hash thay vì sliding).
• Window có thể fixed size (k cho trước) hay variable (mở/co theo condition).

Minimum Window Substring (LC 76) - need / have trace

S = "ADOBECODEBANC", T = "ABC"
need = {A:1, B:1, C:1}; need_unique = 3
have_unique = số ký tự đã match đủ.

window mở rộng tới khi have_unique == need_unique
→ co trái cho đến khi mất 1 ký tự cần thiết → cập nhật min.

Bug điển hình: nhầm “match đủ” với “tổng count đủ”. Chỉ tăng have_unique khi cnt[c] == need[c] (vừa khớp), giảm khi cnt[c] < need[c] (vừa thiếu).

Exactly K = atMost(K) - atMost(K-1)

• Đếm subarray có chính xác K đặc trưng (vd K loại số khác nhau) khó trực tiếp.
• atMost(K) thường dễ với sliding window.
• ⇒ exactly(K) = atMost(K) - atMost(K-1). Áp dụng: LC 992, 1248, 930.

Fixed vs Variable vs atMost

Loại	Pattern	Bài
Fixed k	Window size k, slide 1 bước	LC 643, 567
Variable shrink khi vi phạm	Mở r, co l đến khi hợp lệ	LC 3, 76, 209
atMost K	Mở r, co l đến khi < K đặc tính	LC 992, 1248

---