Sliding Window (cửa sổ trượt) là một kỹ thuật thường được sử dụng để xử lý các dãy liên tiếp trong mảng hoặc chuỗi một cách hiệu quả, bằng cách duy trì một "cửa sổ" chứa một phần tử liên tục của dữ liệu và di chuyển nó qua toàn bộ dãy. Kỹ thuật này giúp biến các giải pháp lồng nhau với độ phức tạp O(n²) thành một vòng lặp đơn với độ phức tạp O(n). Nó đặc biệt hữu ích với các bài toán yêu cầu tìm kiếm dãy con (subarray hoặc substring) thỏa mãn một điều kiện nào đó trong chuỗi hoặc mảng.

Sliding Window Hoạt Động Như Thế Nào?

Có hai dạng phổ biến của thuật toán Sliding Window:

1. Cửa Sổ Có Kích Thước Cố Định (Fixed-Size)

Dạng này được dùng khi kích thước cửa sổ k đã được cho trước, ví dụ: “tìm tổng lớn nhất của một đoạn con gồm k phần tử liên tiếp”. Cách tiếp cận như sau:

Khởi tạo: Tính tổng của k phần tử đầu tiên.

Trượt cửa sổ: Ở mỗi bước, loại bỏ phần tử đầu tiên khỏi tổng, thêm phần tử mới vào cửa sổ.

Cập nhật kết quả: So sánh và lưu lại tổng lớn nhất (hoặc nhỏ nhất).

Tiếp tục: Lặp lại cho đến hết mảng.

Ví dụ: Với arr = [5, 2, -1, 0, 3], k = 3, tổng đầu tiên là 6. Trượt sang phải, tổng tiếp theo là 1, rồi 2. Tổng lớn nhất là 6.

2. Cửa Sổ Có Kích Thước Linh Hoạt (Variable-Size)

Dùng khi độ dài của đoạn con không cố định, nhưng phụ thuộc vào điều kiện (ví dụ: tổng ≥ S, không quá K ký tự khác nhau,...). Các bước như sau:

Mở rộng cửa sổ: Dùng hai con trỏ (left, right) để mở rộng cửa sổ về bên phải cho đến khi thỏa điều kiện.

Thu hẹp từ bên trái: Khi điều kiện bị vi phạm, thu hẹp cửa sổ bằng cách di chuyển con trỏ trái sang phải.

Ghi nhận kết quả: Lưu kết quả mỗi khi điều kiện thỏa mãn.

Tiếp tục: Di chuyển con trỏ phải cho đến hết chuỗi hoặc mảng.

Đây là kỹ thuật hai con trỏ, trong đó mỗi phần tử chỉ bị duyệt tối đa 2 lần, giúp đạt hiệu suất O(n).

Bài Toán Mẫu: Tổng Lớn Nhất Của Đoạn Con Kích Thước K#

Đề bài: Cho một mảng các số nguyên và số k, tìm tổng lớn nhất của bất kỳ đoạn con liên tiếp nào có độ dài k.

Giải pháp Sliding Window bằng Python:

def max_subarray_sum_k(arr, k): n = len(arr) if n < k: raise ValueError("k lớn hơn độ dài mảng") window_sum = sum(arr[:k]) max_sum = window_sum for i in range(k, n): window_sum += arr[i] - arr[i - k] max_sum = max(max_sum, window_sum) return max_sum

Ví dụ:

print(max_subarray_sum_k([100, 200, 300, 400], 2)) # Kết quả: 700

Thay vì tính tổng từ đầu mỗi lần, ta chỉ cập nhật tổng bằng cách trừ đi phần tử cũ và cộng phần tử mới — giúp giảm độ phức tạp từ O(n*k) xuống O(n).

Khi Nào Nên Dùng Sliding Window?

Hãy cân nhắc sử dụng Sliding Window khi:

• Bài toán yêu cầu xử lý đoạn liên tiếp (subarray, substring).
• Cần tìm giá trị tối ưu (tối đa, tối thiểu, thỏa điều kiện) trong một dãy con liên tiếp.
• Câu hỏi nhắc đến kích thước k cố định → dùng cửa sổ cố định.
• Câu hỏi nhắc đến điều kiện linh hoạt → dùng cửa sổ biến đổi.
• Bài toán duyệt nhiều đoạn con có phần trùng lặp → sliding window giúp tiết kiệm thời gian.
• Dữ liệu đến theo luồng (streaming data) hoặc cần xử lý theo thời gian thực.
• Các Bài Tập Kinh Điển Để Luyện Tập Sliding Window
• Dưới đây là một số bài toán điển hình nên luyện tập:
• Tổng lớn nhất đoạn con độ dài K (như bài mẫu ở trên).
• Chuỗi con dài nhất có K ký tự khác nhau.
• Đếm chuỗi con là hoán vị (anagram) của một chuỗi cho trước.
• Chuỗi con nhỏ nhất có chứa tất cả ký tự của chuỗi T.
• Đếm đoạn con có tổng ≥ S (hoặc ≤ S).
• Chuỗi dài nhất chứa nhiều nhất K lần thay đổi ký tự.
• "Fruit Into Baskets": tối đa 2 loại ký tự trong một chuỗi con.
• Dãy con sản phẩm < K.
• Tối đa số 1 liên tiếp sau khi đổi tối đa 1 số 0.
• Sliding Window Maximum: tìm giá trị lớn nhất trong mỗi cửa sổ trượt.

Những bài toán này đều xuất hiện thường xuyên trong các buổi phỏng vấn coding và là cách tốt để rèn luyện khả năng nhận biết và áp dụng Sliding Window.

Kết Luận

Sliding Window là một công cụ mạnh mẽ, giúp giải quyết hiệu quả các bài toán liên quan đến chuỗi hoặc mảng liên tiếp. Khi được áp dụng đúng, nó giúp giảm đáng kể độ phức tạp và tối ưu hiệu năng. Là một lập trình viên chuẩn bị cho phỏng vấn kỹ thuật, bạn nên thành thạo kỹ thuật này. Hãy luyện tập nhiều bài toán đa dạng để rèn kỹ năng nhận diện bài toán phù hợp và triển khai sliding window một cách trơn tru.