Phỏng vấn

Mẫu cửa sổ trượt (Sliding Window) trong phỏng vấn

Cửa sổ trượt (Sliding Window) biến các bài toán duyệt đoạn con liên tiếp từ O(n²) xuống O(n) nhờ giữ hai con trỏ l và r chỉ tiến về phía trước. Nắm vững khi nào mở rộng biên phải, khi nào co biên trái và cách duy trì bộ đếm tần suất sẽ giúp bạn xử lý gọn nhóm bài xâu con trong phỏng vấn.

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 t là "AABC", cửa sổ hợp lệ trong s phả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 s nhỏ hơn độ dài t), 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.

Ý chính

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).

Cửa sổ trượt cực tiểu: s = "ADOBECODEBANC", t = "ABC" Mở rộng r để đủ ký tự của t (missing == 0), rồi thu hẹp l để lấy cửa sổ ngắn nhất 0A1D2O3B4E5C6O7D8E9B10A11N12C Cửa sổ #1: [0..5] = "ADOBEC" (dài 6) Cực tiểu: [9..12] = "BANC" (dài 4) Pha mở rộng r: giảm missing về 0 Pha co l: giữ missing == 0, cực tiểu r-l+1 Mỗi chỉ số vào/ra cửa sổ đúng 1 lần · Độ phức tạp O(|s| + |t|)
Sliding Window: s = "ADOBECODEBANC" Tìm đoạn ngắn nhất chứa đủ t = "ABC" 1. Cửa sổ hợp lệ đầu: s[0..5] "ADOBEC" (dài 6) · đủ A, B, C 2. Trượt tiếp & co l: s[5..10] "CODEBA" (dài 6) · đủ A, B, C 3. Cửa sổ cực tiểu: s[9..12] "BANC" (dài 4) · Đáp án ngắn nhất Hai con trỏ l, r chỉ tăng · O(|s| + |t|)
Hình 1. Quá trình mở rộng biên phải r và co biên trái l của cửa sổ trượt trên chuỗi s = "ADOBECODEBANC" với mẫu t = "ABC" để thu được cửa sổ cực tiểu "BANC" dài 4.

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:

  1. 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 đưa s[r] vào làm tần suất của s[r] vượt quá 1 (cửa sổ trở nên vi phạm), vòng lặp while sẽ tăng l và giảm tần suất s[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òng while, ta mới cập nhật độ dài lớn nhất ans = max(ans, r - l + 1).
  2. 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 r cho đến khi cửa sổ [l..r] chứa đủ mọi ký tự của t theo đúng số lượng yêu cầu (cửa sổ trở nên hợp lệ). Ngay bên trong vòng lặp while (hợp_lệ), ta ghi nhận ứng viên ngắn nhất r - l + 1, rồi chủ động đẩy l sang 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ủa t.

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.

Học cùng giảng viên

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;
}

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ỗi t đúng một lần tốn O(|t|). Trong vòng quét chính, con trỏ r tăng từ 0 đến |s| - 1 (|s| bước), và con trỏ l cũ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ật need và missing trong mỗi bước đều là O(1).
  • Bộ nhớ phụ: O(|Σ|) với |Σ| = 128 cho bảng mã ASCII (tức O(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 char trê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ảng need[c], bạn nên ép kiểu sang unsigned 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.Counter cự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ề 0 mà không ném KeyError.
    • Trong Java 21, truy cập s.charAt(i) và mảng nguyên thủy int[] need = new int[128] tránh được hoàn toàn chi phí autoboxing của HashMap<Character, Integer>, giúp code chạy nhanh hơn rõ rệt trên chuỗi dài 10^5 ký tự.

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:

  1. Khởi tạo missing = t.length() nhưng lại giảm missing chỉ khi need[c] == 0: Nếu t = "AA", t.length() bằng 2 nhưng chỉ có 1 loại ký tự 'A'. Bạn phải nhất quán một trong hai quy ước: hoặc missing đếm số loại ký tự phân biệt (tăng khi need[c] từ 0 lên 1, giảm khi need[c] từ 1 về 0), hoặc đếm tổng số ký tự (giảm mỗi khi need[rc] > 0 trước lúc trừ). Trộn lẫn hai quy ước này sẽ khiến missing không bao giờ về 0 khi t có ký tự lặp.
  2. Cắt chuỗi con ngay trong vòng lặp while: Viết ans = 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ành O(|s|^2), dễ bị quá thời gian (Time Limit Exceeded) trên test lớn.
  3. Quên trường hợp không tìm thấy cửa sổ: Khởi tạo best_len = s.size() + 1 nhưng cuối hàm không kiểm tra best_len > s.size() mà gọi thẳng substr, dẫn tới trả về toàn bộ chuỗi s thay vì chuỗi rỗng.
  4. 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ải r - 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 s ngắn hơn t (ví dụ s = "a", t = "aa" → không có đáp án).
  • Chuỗi s và t dài đúng 1 ký tự trùng nhau (s = "a", t = "a" → trả về "a").
  • Mẫu t có 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.

Muốn học bài bản cùng giảng viên?

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.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483