Pattern — Sliding Window

Khi nào dùng

Bài có substring/subarray + “longest / shortest / contains all / sum at most K”. Window thường mở rộng right, thu hẹp left khi vi phạm constraint.

Decision tree

Window size cố định K?
├─ YES → Fixed window — slide từng bước, maintain aggregate
└─ NO  → Variable window
        ├─ Tìm LONGEST satisfying constraint → expand right, shrink left khi vi phạm
        ├─ Tìm SHORTEST satisfying constraint → expand right; khi đạt → shrink left tối đa
        └─ Đếm số window → Atmost(K) - Atmost(K-1) trick

Templates

Variable longest

let left = 0, best = 0;
for (let right = 0; right < n; right++) {
  // Add nums[right]
  while (/* invariant violated */) {
    // Remove nums[left++]
  }
  best = Math.max(best, right - left + 1);
}

Variable shortest

let left = 0, best = Infinity;
for (let right = 0; right < n; right++) {
  // Add nums[right]
  while (/* invariant satisfied */) {
    best = Math.min(best, right - left + 1);
    // Remove nums[left++]
  }
}

Atmost trick (đếm subarrays)

exactly(K) = atmost(K) - atmost(K-1). Dùng khi tính số subarrays với điều kiện ==K.

Top problems

Bài	LC	Loại
Longest Substring No Repeat	LC #3	Variable longest
Min Window Substring	LC #76	Variable shortest + freq map
Longest Repeating Char Replace	LC #424	Variable longest + maxFreq
Permutation in String	LC #567	Fixed K + freq compare
Sliding Window Max	LC #239	Monotonic deque
Subarrays with K Different	LC #992	Atmost trick
Min Size Subarray Sum	LC #209	Variable shortest
Fruit Into Baskets	LC #904	Atmost(2)

Pitfalls

1. Khi shrink trong “longest”: while (violated) không phải if.
2. maxFreq trong LC #424: KHÔNG cần update khi shrink — explanation tinh tế.
3. Đối với character map: nhớ giảm count khi left++, kiểm tra formed === required invariant.
4. Đối với fixed window: chỉ record kết quả khi right >= K - 1.

→ Nguồn lý thuyết: 01-Two-Pointers-Sliding-Window