Lesson 14 — Sliding Window (Cửa sổ trượt)
3 module tương tác: (1) Fixed window — trượt cửa sổ độ dài k, thấy tổng được tái dùng (trừ trái + cộng phải, không tính lại); (2) Variable window — longest substring không lặp, animate mở rộng/thu nhỏ theo hash; (3) Window maximum — deque đơn điệu giữ max của mỗi window.
1. Fixed window: tổng tái dùng
Mảng cố định k. Mỗi bước trượt: phần tử trái rơi ra, phần tử phải lọt vào. Tổng mới = tổng cũ − trái + phải (O(1)).
2. Variable window: longest substring không lặp
Mở rộng r mỗi bước. Nếu s[r] đã có trong window (gây lặp), nhảy l qua bản sao cũ (window co lại). Cập nhật độ dài lớn nhất.
Thử: nhập chuỗi có ký tự lặp — cửa sổ co biên trái đúng lúc gặp trùng: mỗi phần tử vào/ra tối đa 1 lần → O(n).
3. Window maximum: deque đơn điệu
Deque giữ chỉ số, giá trị giảm dần từ front→back. Push: bỏ các back ≤ giá trị mới. Bỏ front nếu trôi ra ngoài window. Front luôn là max của window.