Nhận diện bài toán cửa sổ trượt và hợp đồng cần hỏi rõ
Trong các bộ đề luyện phỏng vấn thuật toán, nhóm câu hỏi về đoạn con liên tiếp (contiguous subarray) và xâu con liên tiếp (substring) là một dạng quen thuộc. Hai đại diện tiêu biểu nhất là bài toán tìm xâu con dài nhất không lặp (Longest Substring Without Repeating Characters) và tìm cửa sổ con ngắn nhất chứa đủ ký tự mẫu (Minimum Window Substring). Dù câu chữ khác nhau, cả hai đều hỏi về một đoạn chỉ số liên tiếp [l..r] tối ưu hóa độ dài dưới một ràng buộc tần suất ký tự. Nếu bạn chưa quen kỹ thuật này trên mảng số (cửa sổ cố định dài k, cửa sổ co giãn theo tổng), hãy đọc trước bài kỹ thuật cửa sổ trượt.
Trước khi đặt bút viết dòng code đầu tiên, bạn nên trao đổi ngắn gọn với người phỏng vấn để khóa chặt đặc tả đầu vào và đầu ra:
- Tập ký tự (Alphabet): Chuỗi chỉ gồm chữ cái tiếng Anh viết hoa, viết thường, chữ số hay toàn bộ bảng mã ASCII 128 ký tự? Nếu là ASCII chuẩn, một mảng tĩnh
int[128]sẽ nhanh và gọn hơn rất nhiều so với bảng băm tổng quát. - Xử lý ký tự trùng trong mẫu: Với bài Minimum Window Substring, nếu chuỗi mẫu
tlà"AABC", cửa sổ hợp lệ trongsphải chứa ít nhất hai chữ'A', một chữ'B'và một chữ'C', chứ không chỉ kiểm tra sự có mặt theo tập hợp. - Quy ước khi không có đáp án hoặc hòa kết quả: Nếu không tồn tại cửa sổ nào thỏa mãn (ví dụ độ dài
snhỏ hơn độ dàit), hàm trả về chuỗi rỗng""hay một nhãn đặc biệt? Nếu có nhiều cửa sổ cùng đạt độ dài ngắn nhất, bài toán cần cửa sổ xuất hiện đầu tiên từ trái sang phải hay bất kỳ cửa sổ nào? - Phân biệt Substring và Subsequence: Cửa sổ trượt chỉ áp dụng cho đoạn liên tiếp (substring). Nếu đề bài hỏi dãy con không cần liên tiếp (subsequence), mô hình sẽ chuyển sang hai con trỏ trên hai chuỗi hoặc quy hoạch động.
Việc nêu rõ bốn câu hỏi này chỉ mất chưa tới một phút nhưng giúp bạn tránh viết nhầm cấu trúc dữ liệu (chẳng hạn dùng HashSet thay vì bảng đếm tần suất) và tạo ấn tượng về tư duy làm việc cẩn thận.
Bản chất của cửa sổ trượt kích thước biến thiên là tính đơn điệu của hai biên: khi biên phải r tiến thêm một bước, biên trái l chỉ có thể đứng yên hoặc tiến lên, không bao giờ lùi lại. Nhờ mỗi phần tử vào cửa sổ đúng một lần và rời cửa sổ tối đa một lần, tổng số thao tác cập nhật trên toàn bộ quá trình quét chỉ là O(n).
Hai khuôn cửa sổ trượt biến thiên: Tìm đoạn dài nhất và tìm đoạn ngắn nhất
Hầu hết ứng viên đều nhớ mang máng rằng cửa sổ trượt gồm một vòng lặp for cho r và một vòng lặp while bên trong để dịch l. Tuy nhiên, điều kiện của vòng while và vị trí cập nhật đáp án lại hoàn toàn ngược nhau giữa bài toán tìm cực đại và bài toán tìm cực tiểu:
- Khuôn cực đại (như Xâu con dài nhất không lặp): Cửa sổ hợp lệ khi mọi ký tự trong
[l..r]đều có tần suất không vượt quá1. Khi đưas[r]vào làm tần suất củas[r]vượt quá1(cửa sổ trở nên vi phạm), vòng lặpwhilesẽ tănglvà giảm tần suấts[l]cho tới khi cửa sổ quay lại trạng thái hợp lệ. Lúc này, bên ngoài vòngwhile, ta mới cập nhật độ dài lớn nhấtans = max(ans, r - l + 1). - Khuôn cực tiểu (như Minimum Window Substring): Cửa sổ ban đầu chưa đủ ký tự nên chưa hợp lệ. Ta mở rộng
rcho đến khi cửa sổ[l..r]chứa đủ mọi ký tự củattheo đúng số lượng yêu cầu (cửa sổ trở nên hợp lệ). Ngay bên trong vòng lặpwhile (hợp_lệ), ta ghi nhận ứng viên ngắn nhấtr - l + 1, rồi chủ động đẩylsang phải để thử cắt bớt phần thừa cho tới khi cửa sổ thiếu ít nhất một ký tự củat.
Nếu viết một hàm kiểm tra điều kiện hợp lệ bằng cách quét lại toàn bộ 26 hoặc 128 ký tự ở mỗi bước, độ phức tạp sẽ bị đội lên O(|Σ| * n). Bí quyết để đạt O(|s| + |t|) thuần túy là duy trì một biến nguyên duy nhất missing đếm số loại ký tự phân biệt trong t vẫn còn thiếu so với nhu cầu.
Chạy tay từng bước trên ví dụ s = "ADOBECODEBANC", t = "ABC"
Hãy theo dõi cách mảng nhu cầu need và biến missing vận hành trên dữ liệu mẫu kinh điển s = "ADOBECODEBANC", t = "ABC". Đầu tiên, ta quét t = "ABC" để khởi tạo need['A'] = 1, need['B'] = 1, need['C'] = 1 và số loại ký tự đang thiếu là missing = 3.
Khi con trỏ phải r đi qua từng ký tự rc = s[r], ta giảm need[rc] đi 1 (nghĩa là nhu cầu về ký tự rc đã được đáp ứng thêm một đơn vị; nếu need[rc] âm thì cửa sổ đang dư ký tự đó). Khoảnh khắc need[rc] giảm từ 1 về đúng 0, loại ký tự rc vừa đủ định mức nên ta giảm missing đi 1.
Khi missing == 0, cửa sổ [l..r] đang chứa đủ 'A', 'B', 'C'. Ta cập nhật đáp án nếu độ dài r - l + 1 nhỏ hơn best_len, sau đó nhấc lc = s[l] ra khỏi cửa sổ và tăng l. Nếu trước khi nhấc ra mà need[lc] == 0 (tức là ký tự lc vừa khít định mức, không dư), việc bỏ lc khiến cửa sổ thiếu lại loại ký tự đó nên missing tăng lên 1 và vòng while dừng lại.
| Bước | Biên r và s[r] |
Trạng thái cửa sổ trước khi co l |
Diễn biến co biên trái l khi missing == 0 |
Cửa sổ tốt nhất lưu lại |
|---|---|---|---|---|
| 1 | r = 0..5 (A..C) |
[0..5] = "ADOBEC" làm missing về 0 |
Ghi nhận "ADOBEC" (dài 6); bỏ 'A' tại l = 0 làm need['A'] = 1, missing = 1, dừng co tại l = 1 |
"ADOBEC" (best_l = 0, best_len = 6) |
| 2 | r = 6..10 (O..A) |
Tại r = 10 ('A'), cửa sổ [1..10] = "DOBECODEBA" có hai chữ 'B', 'O', 'D', 'E' và đủ A, B, C |
Co l qua D(1), O(2), B(3), E(4) vì đều dư hoặc không thuộc t; tới [5..10] = "CODEBA" (dài 6), bỏ 'C' tại l = 5 làm missing = 1, dừng ở l = 6 |
"ADOBEC" (best_l = 0, best_len = 6) |
| 3 | r = 11 ('N') |
[6..11] = "ODEBAN", vẫn thiếu 'C' (missing = 1) |
Không vào vòng while vì missing == 1 |
"ADOBEC" (best_l = 0, best_len = 6) |
| 4 | r = 12 ('C') |
[6..12] = "ODEBANC" làm need['C'] = 0, missing = 0 |
Co l bỏ O(6), D(7) tới [8..12] = "EBANC" (dài 5 < 6, cập nhật); bỏ tiếp E(8) tới [9..12] = "BANC" (dài 4 < 5, cập nhật lần nữa); bỏ 'B' tại l = 9 làm missing = 1, dừng ở l = 10 |
"BANC" (best_l = 9, best_len = 4) |
Bảng chạy tay cho thấy rõ vì sao thuật toán không bao giờ bỏ sót đáp án: mỗi khi r chạm tới ký tự hoàn tất bộ mẫu, việc co l tối đa sẽ tìm ra cửa sổ ngắn nhất kết thúc tại đúng chỉ số r đó. Lấy giá trị nhỏ nhất qua mọi r chính là cửa sổ ngắn nhất trên toàn chuỗi.
Chủ đề này nằm trong Tuần 3-4: Sliding Window & Linked List của Khóa LeetCode. Xem đề cương
Code mẫu C++17, Python và Java 21
Chương trình dưới đây cài đặt hoàn chỉnh thuật toán tìm cửa sổ con ngắn nhất trên cả 3 ngôn ngữ. Nếu không truyền dữ liệu vào từ luồng nhập chuẩn, chương trình tự chạy trên bộ mẫu "ADOBECODEBANC" và "ABC" để in ra "BANC"; nếu không có cửa sổ hợp lệ thì in "NONE".
#include <array>
#include <iostream>
#include <string>
using namespace std;
string min_window(const string& s, const string& t) {
if (t.empty() || s.size() < t.size()) return "NONE";
array<int, 128> need{};
int missing = 0;
for (unsigned char c : t) {
if (need[c] == 0) missing++;
need[c]++;
}
int best_l = 0, best_len = (int)s.size() + 1;
int l = 0;
for (int r = 0; r < (int)s.size(); r++) {
unsigned char rc = s[r];
need[rc]--;
if (need[rc] == 0) missing--;
while (missing == 0) {
if (r - l + 1 < best_len) {
best_len = r - l + 1;
best_l = l;
}
unsigned char lc = s[l++];
if (need[lc] == 0) missing++;
need[lc]++;
}
}
return best_len > (int)s.size() ? "NONE" : s.substr(best_l, best_len);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s = "ADOBECODEBANC", t = "ABC";
if (!(cin >> s >> t)) {
s = "ADOBECODEBANC";
t = "ABC";
}
cout << min_window(s, t) << '\n';
return 0;
}
import collections
import sys
def min_window(s: str, t: str) -> str:
if not t or len(s) < len(t):
return "NONE"
need = collections.Counter(t)
missing = len(need)
best_l, best_len = 0, len(s) + 1
l = 0
for r, ch in enumerate(s):
need[ch] -= 1
if need[ch] == 0:
missing -= 1
while missing == 0:
if r - l + 1 < best_len:
best_len = r - l + 1
best_l = l
left_ch = s[l]
l += 1
if need[left_ch] == 0:
missing += 1
need[left_ch] += 1
return "NONE" if best_len > len(s) else s[best_l : best_l + best_len]
def main() -> None:
tokens = sys.stdin.read().split()
s, t = (tokens[0], tokens[1]) if len(tokens) >= 2 else ("ADOBECODEBANC", "ABC")
print(min_window(s, t))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static String minWindow(String s, String t) {
if (t.isEmpty() || s.length() < t.length()) return "NONE";
int[] need = new int[128];
int missing = 0;
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
if (need[c] == 0) missing++;
need[c]++;
}
int bestL = 0, bestLen = s.length() + 1;
int l = 0;
for (int r = 0; r < s.length(); r++) {
char rc = s.charAt(r);
need[rc]--;
if (need[rc] == 0) missing--;
while (missing == 0) {
if (r - l + 1 < bestLen) {
bestLen = r - l + 1;
bestL = l;
}
char lc = s.charAt(l++);
if (need[lc] == 0) missing++;
need[lc]++;
}
}
return bestLen > s.length() ? "NONE" : s.substring(bestL, bestL + bestLen);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = "ADOBECODEBANC", t = "ABC";
if (sc.hasNext()) {
s = sc.next();
if (sc.hasNext()) t = sc.next();
}
System.out.println(minWindow(s, t));
}
}
Một chi tiết kỹ thuật rất đáng lưu ý là thay vì cắt chuỗi con s.substr(l, r - l + 1) mỗi lần tìm thấy ứng viên mới bên trong vòng lặp — thao tác tốn O(k) thời gian và cấp phát bộ nhớ liên tục — ta chỉ lưu hai số nguyên best_l và best_len. Chỉ khi kết thúc toàn bộ vòng quét, hàm mới trích xuất chuỗi con đúng một lần duy nhất ở dòng return.
Độ phức tạp và lưu ý theo từng ngôn ngữ
- Thời gian:
O(|s| + |t|). Vòng khởi tạo quét qua chuỗitđúng một lần tốnO(|t|). Trong vòng quét chính, con trỏrtăng từ0đến|s| - 1(|s|bước), và con trỏlcũng chỉ tăng đơn điệu từ0đến tối đa|s|(không quá|s|bước). Mọi phép cập nhậtneedvàmissingtrong mỗi bước đều làO(1). - Bộ nhớ phụ:
O(|Σ|)với|Σ| = 128cho bảng mã ASCII (tứcO(1)bộ nhớ phụ theo kích thước chuỗi đầu vào), cộng thêm bộ nhớ tạo chuỗi kết quả lúc trả về. - Đặc thù ngôn ngữ:
- Trong C++17, kiểu
chartrên nhiều trình biên dịch có dấu (signed), nên khi dùng ký tự làm chỉ số mảngneed[c], bạn nên ép kiểu sangunsigned charđể tránh chỉ số âm; nếu dữ liệu có thể chứa ký tự mở rộng (mã 128–255) thì mảng đếm phải có 256 phần tử, vì mảng 128 phần tử chỉ đủ cho ASCII chuẩn. - Trong Python,
collections.Countercực kỳ tiện lợi cho buổi phỏng vấn vì truy cập khóa chưa tồn tại tự trả về0mà không némKeyError. - Trong Java 21, truy cập
s.charAt(i)và mảng nguyên thủyint[] need = new int[128]tránh được hoàn toàn chi phí autoboxing củaHashMap<Character, Integer>, giúp code chạy nhanh hơn rõ rệt trên chuỗi dài10^5ký tự.
- Trong C++17, kiểu
Bảng so sánh các biến thể cửa sổ trượt thường gặp
Khi nắm vững cơ chế hai con trỏ cộng bộ đếm, bạn có thể điều chỉnh đúng một vài dòng kiểm tra trạng thái để giải hàng loạt bài phỏng vấn cùng họ:
| Bài toán phỏng vấn | Điều kiện cửa sổ hợp lệ | Cấu trúc trạng thái cần giữ | Khi nào dịch biên trái l? |
|---|---|---|---|
| Longest Substring Without Repeating Characters | Mọi ký tự trong [l..r] có tần suất <= 1 |
Mảng cnt[128] hoặc last_pos[128] lưu vị trí xuất hiện gần nhất |
Khi cnt[s[r]] > 1 (hoặc nhảy thẳng l = max(l, last_pos[s[r]] + 1)) |
| Minimum Window Substring | Đủ mọi ký tự của t (missing == 0) |
Mảng nhu cầu need[128] và số loại ký tự còn thiếu missing |
Trong khi missing == 0 (vừa cập nhật cực tiểu vừa co l) |
| Longest Repeating Character Replacement | (r - l + 1) - max_freq <= k |
Mảng cnt[26] và tần suất lớn nhất max_freq trong cửa sổ |
Khi số ký tự cần thay vượt quá k thì dịch l đi 1 bước |
| Permutation in String / Find All Anagrams | Độ dài đúng bằng |p| và missing == 0 |
Cửa sổ cố định độ dài |p| cùng mảng need[26] |
Dịch l mỗi khi r - l + 1 > |p| để giữ kích thước cố định |
| Subarray Sum Equals K (có số âm) | Tổng đoạn bằng k (nhưng không dùng cửa sổ trượt được!) |
Bảng băm tần suất tổng tiền tố prefix_sum |
Không dùng hai con trỏ vì có số âm làm mất tính đơn điệu |
Dòng cuối cùng của bảng trên ứng với một câu hỏi mở rộng bạn nên chuẩn bị sẵn: "Nếu mảng có cả số âm và số dương, em có dùng Sliding Window tìm đoạn con tổng >= S ngắn nhất được không?" Câu trả lời chuẩn xác là không, bởi khi có số âm, việc mở rộng r có thể làm tổng giảm xuống và việc co l lại có thể làm tổng tăng lên, phá vỡ bất biến đơn điệu của cửa sổ trượt. Lúc đó ta phải chuyển sang tổng tiền tố kết hợp hàng đợi hai đầu đơn điệu (monotonic deque); bảng băm tổng tiền tố chỉ giải được biến thể tổng đúng bằng k.
Những lỗi sai kinh điển và cách tự kiểm tra code
Trong phòng phỏng vấn áp lực thời gian, ứng viên thường mắc bốn lỗi nhỏ nhưng làm sai kết quả trên các ca biên:
- Khởi tạo
missing = t.length()nhưng lại giảmmissingchỉ khineed[c] == 0: Nếut = "AA",t.length()bằng2nhưng chỉ có1loại ký tự'A'. Bạn phải nhất quán một trong hai quy ước: hoặcmissingđếm số loại ký tự phân biệt (tăng khineed[c]từ0lên1, giảm khineed[c]từ1về0), hoặc đếm tổng số ký tự (giảm mỗi khineed[rc] > 0trước lúc trừ). Trộn lẫn hai quy ước này sẽ khiếnmissingkhông bao giờ về0khitcó ký tự lặp. - Cắt chuỗi con ngay trong vòng lặp
while: Viếtans = s.substring(l, r + 1)ở mỗi bước co làm độ phức tạp trường hợp xấu biến thànhO(|s|^2), dễ bị quá thời gian (Time Limit Exceeded) trên test lớn. - Quên trường hợp không tìm thấy cửa sổ: Khởi tạo
best_len = s.size() + 1nhưng cuối hàm không kiểm trabest_len > s.size()mà gọi thẳngsubstr, dẫn tới trả về toàn bộ chuỗisthay vì chuỗi rỗng. - Nhầm lẫn giữa chỉ số 0-based và độ dài đoạn: Độ dài của cửa sổ đóng
[l..r]luôn làr - l + 1, không phảir - l.
Để tự kiểm tra code trước khi báo hoàn thành với người phỏng vấn, bạn có thể viết nhanh một hàm vét cạn ngắn khoảng 8 dòng: duyệt mọi cặp 0 <= l < r <= |s|, đếm tần suất ký tự của s[l:r] và so sánh với bảng tần suất của t. Sau đó thử đối chiếu hai hàm trên 5 ca biên nhỏ:
- Chuỗi
sngắn hơnt(ví dụs = "a",t = "aa"→ không có đáp án). - Chuỗi
svàtdài đúng 1 ký tự trùng nhau (s = "a",t = "a"→ trả về"a"). - Mẫu
tcó ký tự lặp (s = "xyzyx",t = "xyy"→ đáp án là"xyzy"dài 4: cửa sổ phải chứa đủ hai chữ'y', còn"xyz"vẫn thiếu một chữ'y'). - Ký tự dư thừa nằm dày đặc ở đầu cửa sổ (
s = "abbbcddabcd",t = "abcd"→ cửa sổ hợp lệ đầu tiên là"abbbcd"dài 6, còn đáp án là"dabc"dài 4 bắt đầu ở chỉ số 6). - Cửa sổ ngắn nhất nằm sát mép phải của
s("ADOBECODEBANC","ABC"→"BANC").
Luyện ngay trên Big-O Coding
Bạn hãy thực hành ngay ba bài toán cửa sổ trượt từ cơ bản đến nâng cao trong lộ trình Coding Interview 150 dưới đây để rèn phản xạ đóng mở hai biên l và r.
Câu hỏi thường gặp
Vì sao bên trong vòng lặp for có thêm vòng lặp while nhưng độ phức tạp vẫn là O(n) chứ không phải O(n²)?
Độ phức tạp không phụ thuộc vào số vòng lặp lồng nhau mà phụ thuộc vào tổng số lần thân vòng lặp while thực thi trên toàn bộ chương trình. Vì mỗi lần vòng while chạy thì biến l đều tăng thêm 1 và l không bao giờ giảm, nên qua suốt cả quá trình r chạy từ 0 đến n - 1, thân vòng while chỉ chạy tổng cộng tối đa n lần. Cộng với n bước của r, tổng chi phí là 2n = O(n) theo phân tích khấu hao (amortized analysis).
Khi nào nên dùng mảng tĩnh int[128] và khi nào nên dùng HashMap cho cửa sổ trượt?
Nếu đề bài xác nhận chuỗi chỉ gồm chữ cái tiếng Anh hoặc ký tự ASCII chuẩn, mảng tĩnh int[128] luôn vượt trội nhờ truy cập địa chỉ bộ nhớ liên tiếp trong O(1) với hằng số cực nhỏ. Bạn chỉ cần dùng HashMap (hoặc unordered_map) khi đầu vào là chuỗi Unicode tổng quát chứa hàng chục nghìn mã ký tự hoặc khi cửa sổ trượt áp dụng trên mảng số nguyên có giá trị lớn tới 10^9.
Làm sao để nhảy cóc con trỏ trái l trong bài Xâu con dài nhất không lặp?
Thay vì lưu tần suất và tăng l từng bước một, bạn có thể lưu chỉ số xuất hiện gần nhất last_pos[c] của mỗi ký tự c. Khi gặp s[r] đã xuất hiện tại vị trí last_pos[s[r]] >= l, bạn nhảy thẳng l = last_pos[s[r]] + 1 chỉ trong một phép gán. Hãy nhớ điều kiện >= l (hoặc l = max(l, last_pos[s[r]] + 1)) để con trỏ l không bao giờ bị kéo lùi về vị trí cũ nằm ngoài cửa sổ hiện tại.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


