Minimum Window Substring: cửa sổ biến đổi với coverage counter

Đây là bài trong series sliding-window mà kích thước window hoàn toàn không bị ràng buộc — cả hai pointer có thể di chuyển với tốc độ khác nhau, và bạn vẫn phải giải quyết trong một lần duyệt. Cơ chế two-pointer đến đây đã quen rồi. Điều làm bài 76 thực sự khó là phần kiểm tra tính hợp lệ. Làm sao biết trong O(1) rằng window hiện tại đã cover đủ tất cả ký tự trong t?

Câu trả lời là một counter mà hầu hết các bài giải gọi là have và need — hoặc formed và required. Bài này tập trung vào lý do tại sao counter đó tồn tại và nó đang làm gì.

Bài toán và những gì constraints bắt buộc

Cho hai chuỗi s và t, trả về substring ngắn nhất của s chứa mọi ký tự trong t (bao gồm cả ký tự trùng lặp). Nếu không có substring nào như vậy, trả về "".

s = "ADOBECODEBANC", t = "ABC" -> "BANC".

s = "a", t = "aa" -> "". Cả hai a trong t phải có mặt; s chỉ có một.

Điều khoản về duplicate là thứ hay bẫy người giải. t = "AA" yêu cầu hai A trong window, không phải một. Frequency map — không phải set — mới là cấu trúc dữ liệu đúng.

Đọc kỹ constraints: cả s và t có thể lên đến 10^5 ký tự, và chỉ chứa chữ cái tiếng Anh (hoa và thường). Hai thứ rút ra ngay:

• 10^5 loại bỏ mọi approach O(m²). Cần O(m + n) — nghĩa là duyệt s tối đa một lần. Sliding window là ứng viên rõ ràng nhất.
• "Chỉ chứa chữ cái tiếng Anh" nghĩa là alphabet bị chặn tại 52 ký tự. Có thể thay hash map bằng mảng kích thước cố định int[128] để tăng tốc theo hệ số hằng số, dù không thay đổi asymptotic complexity.

Brute force: O(m² x n)

Cách đọc naive của bài toán: duyệt qua mọi starting index i, mở rộng j sang phải cho đến khi window s[i:j+1] cover được t, ghi lại độ dài, rồi thử i tiếp theo.

Phiên bản dưới đây có thêm break ngay khi tìm thấy window hợp lệ đầu tiên cho i đã cho — không cần mở rộng thêm vì ta muốn window ngắn nhất. Trong best case (window hợp lệ tìm thấy sớm) thì O(m × n) mỗi starting index, nhưng worst case vẫn là O(m²×n) khi không tìm được window hợp lệ nào.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
 
        need = Counter(t)
        min_len = float("inf")
        result = ""
 
        for i in range(len(s)):
            window = {}
            for j in range(i, len(s)):
                c = s[j]
                window[c] = window.get(c, 0) + 1
                if all(window.get(ch, 0) >= cnt for ch, cnt in need.items()):
                    if j - i + 1 < min_len:
                        min_len = j - i + 1
                        result = s[i : j + 1]
                    break  # ngắn nhất cho i này, không cần mở rộng thêm
 
        return result

public class Solution {
    public string MinWindow(string s, string t) {
        var need = new Dictionary<char, int>();
        foreach (char c in t) need[c] = need.GetValueOrDefault(c, 0) + 1;
 
        int minLen = int.MaxValue;
        string result = "";
 
        for (int i = 0; i < s.Length; i++) {
            var window = new Dictionary<char, int>();
            for (int j = i; j < s.Length; j++) {
                char c = s[j];
                window[c] = window.GetValueOrDefault(c, 0) + 1;
                bool valid = true;
                foreach (var kv in need)
                    if (window.GetValueOrDefault(kv.Key, 0) < kv.Value) { valid = false; break; }
                if (valid) {
                    if (j - i + 1 < minLen) { minLen = j - i + 1; result = s.Substring(i, j - i + 1); }
                    break;
                }
            }
        }
        return result;
    }
}

Với m = n = 10^5 và không có window hợp lệ, approach này chạm O(m²×n) — hoàn toàn không dùng được. Phần kiểm tra tính hợp lệ phải scan toàn bộ need map ở mỗi bước. Cần cách để biết — mà không scan gì cả — liệu window hiện tại có hợp lệ không.

Insight then chốt: đếm số ký tự đã thỏa mãn, không phải tất cả ký tự

Trước khi sliding, xây frequency map của t:

need = {'A': 1, 'B': 1, 'C': 1}   (với t = "ABC")
required = 3                        (len(need) — số ký tự distinct cần thỏa mãn)

Sau đó duy trì một frequency map thứ hai window_counts cho các ký tự trong window hiện tại, và một integer have đếm có bao nhiêu trong required ký tự distinct đang được thỏa mãn.

Một ký tự c được coi là "thỏa mãn" khi window_counts[c] >= need[c]. Quan trọng là, have chỉ thay đổi tại các ngưỡng chính xác:

• Tăng have khi thêm s[right] khiến window_counts[c] đạt đúng need[c] (từ chưa thỏa mãn sang thỏa mãn).
• Giảm have khi bỏ s[left] khiến window_counts[c] giảm xuống dưới need[c] (từ thỏa mãn sang chưa thỏa mãn).

Khi have == required, window hợp lệ. Không cần scan map — chỉ là một phép so sánh integer.

State machine của thuật toán trông như thế này:

Giải pháp sliding window

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
 
        from collections import Counter
        need = Counter(t)
        required = len(need)
 
        left = 0
        have = 0
        window_counts = {}
 
        best_len = float("inf")
        best_left = 0
 
        for right in range(len(s)):
            c = s[right]
            window_counts[c] = window_counts.get(c, 0) + 1
 
            # Thêm c có khiến ký tự này đạt ngưỡng thỏa mãn không?
            if c in need and window_counts[c] == need[c]:
                have += 1
 
            # Thu nhỏ từ trái khi window đang hợp lệ
            while have == required:
                # Ghi lại nếu đây là window tốt nhất cho đến nay
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_left = left
 
                # Bỏ ký tự ngoài cùng bên trái
                left_c = s[left]
                window_counts[left_c] -= 1
                if left_c in need and window_counts[left_c] < need[left_c]:
                    have -= 1
                left += 1
 
        return "" if best_len == float("inf") else s[best_left : best_left + best_len]

public class Solution {
    public string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
 
        var need = new Dictionary<char, int>();
        foreach (char c in t) need[c] = need.GetValueOrDefault(c, 0) + 1;
        int required = need.Count;
 
        var windowCounts = new Dictionary<char, int>();
        int left = 0, have = 0;
        int bestLen = int.MaxValue, bestLeft = 0;
 
        for (int right = 0; right < s.Length; right++) {
            char c = s[right];
            windowCounts[c] = windowCounts.GetValueOrDefault(c, 0) + 1;
 
            if (need.ContainsKey(c) && windowCounts[c] == need[c])
                have++;
 
            while (have == required) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestLeft = left;
                }
                char lc = s[left];
                windowCounts[lc]--;
                if (need.ContainsKey(lc) && windowCounts[lc] < need[lc])
                    have--;
                left++;
            }
        }
 
        return bestLen == int.MaxValue ? "" : s.Substring(bestLeft, bestLen);
    }
}

Đi qua ví dụ từng bước

s = "ADOBECODEBANC", t = "ABC".

Trạng thái ban đầu: need = {A:1, B:1, C:1}, required = 3, have = 0, left = 0.

Giai đoạn 1 — mở rộng right cho đến khi hợp lệ:

Window s[0:6] = "ADOBEC", độ dài 6. Ghi lại best.

Giai đoạn 1 — thu nhỏ từ left:

Bỏ A (left=0): window_counts[A] giảm về 0, dưới need[A]=1 -> have=2. left=1. Không còn hợp lệ, dừng thu nhỏ.

Giai đoạn 2 — mở rộng right tiếp:

Window hợp lệ tại left=1. Thu nhỏ:

• Bỏ D (left=1): không trong need, left=2.
• Bỏ O (left=2): không trong need, left=3.
• Bỏ B (left=3): window_counts[B] giảm từ 2 xuống 1, vẫn >= need[B]=1, have vẫn là 3. left=4.
• Bỏ E (left=4): không trong need, left=5.
• Tại left=5, trước khi bỏ: window là s[5:11] = "CODEBA", độ dài 6. Không cải thiện.
• Bỏ C (left=5): window_counts[C] về 0 < need[C]=1 -> have=2. left=6.

Giai đoạn 3 — mở rộng tiếp:

Window hợp lệ tại left=6. Thu nhỏ:

• Bỏ O (left=6): không trong need, left=7.
• Bỏ D (left=7): không trong need, left=8.
• Bỏ E (left=8): không trong need, left=9.
• Tại left=9, trước khi bỏ: window là s[9:13] = "BANC", độ dài 4. Best mới. best_left=9, best_len=4.
• Bỏ B (left=9): window_counts[B] về 0 < need[B]=1 -> have=2. left=10.

right chạy hết chuỗi. Trả về s[9:13] = "BANC".

Tại sao coverage counter là toàn bộ trick

Không có have, bạn phải kiểm tra xem tất cả các entry trong need đã thỏa mãn chưa mỗi khi muốn thu nhỏ. Đó là O(|need|) mỗi bước — thực tế là O(26) cho ASCII letters — không thay đổi asymptotic complexity nhưng thêm constant factor tích lũy.

Quan trọng hơn, threshold check (window_counts[c] == need[c]) là khoảnh khắc chính xác mà một ký tự chuyển từ chưa thỏa mãn sang thỏa mãn. Nó chỉ xảy ra nhiều nhất một lần mỗi ký tự trong mỗi lần mở rộng window. Counter chuyển đổi một lần scan map thành một phép so sánh counter. Cùng thông tin, O(1) mỗi bước.

Ý tưởng tương tự xuất hiện bất cứ khi nào cần biết liệu sliding window có thỏa mãn frequency constraint không. Permutation in String (567) dùng counter y hệt. Longest Substring Without Repeating Characters (3) không cần — uniqueness là constraint khác — nhưng vòng lặp shrink-when-invalid có cùng cấu trúc.

So sánh các approach

Giới hạn space cho giải pháp tối ưu thực tế là O(alphabet size) vì cả hai map đều bị chặn bởi số ký tự distinct — O(1) cho ASCII letters. Với ký tự Unicode tùy ý thì là O(m + n) worst case. Với bài toán có constraints (chỉ chữ cái tiếng Anh), bạn có thể đổi cả hai hash map thành mảng int[128] để cải thiện rõ rệt về constant factor.

Tôi sẽ ship sliding window. Brute force có giá trị sư phạm nhưng sẽ chạm tường ngay với 10^5 ký tự.

Edge cases và cách code xử lý

s ngắn hơn t. Không window nào chứa được đủ t, nên have không bao giờ đạt required và vòng lặp thoát bình thường. Code trả về "" vì best_len vẫn là vô cực. Có thể thêm kiểm tra sớm (if len(s) < len(t): return "") để tránh vòng lặp không cần thiết.

t có ký tự không có trong s. Tương tự: have không bao giờ đạt required. Không cần xử lý đặc biệt — vòng lặp chính chạy hết s mà vòng lặp while bên trong không bao giờ kích hoạt.

t có duplicate như "AA". Nguồn bug phổ biến nhất. need['A'] = 2, nên have chỉ tăng khi window_counts['A'] đạt đúng 2. Window với một A không làm have thay đổi gì. Frequency map xử lý điều này đúng miễn là so sánh count, không chỉ kiểm tra sự có mặt.

s == t. Window hợp lệ đầu tiên tìm được chính là toàn bộ chuỗi. Code ghi lại nó, rồi thử thu nhỏ — nhưng thu nhỏ luôn làm have giảm ngay vì mỗi ký tự trong window đều được cần đúng một lần. Trả về s nguyên vẹn.

s = "a", t = "a". right=0 thêm A, have đạt 1 == required, ghi best_len=1, rồi thu nhỏ: bỏ A làm have về 0, left=1. Vòng lặp thoát. Trả về "a". Đúng.

Vị trí trong series: bài này thêm gì

Trong series sliding-window, các bài trước có kích thước window cố định hoặc có thể dự đoán được. Longest Substring Without Repeating Characters (3) đã giới thiệu pattern shrink-when-invalid, nhưng kiểm tra tính hợp lệ ở đó đơn giản: ký tự đến có đã trong window không? Set và một if là đủ.

Bài 76 thêm hai phức tạp cùng một lúc: tính hợp lệ của window bây giờ phụ thuộc vào frequency constraint (không chỉ sự có mặt), và bạn đang tối thiểu hóa kích thước window thay vì tối đa hóa. Coverage counter là câu trả lời cho phần frequency. Pattern minimise-on-shrink (ghi lại best, rồi thu nhỏ) là câu trả lời cho phần hướng.

Sau bài này, bước tự nhiên tiếp theo là các bài có điều kiện window hợp lệ phụ thuộc vào nhiều constraints độc lập — ví dụ sliding window qua các phần tử có màu sắc mà bạn cần đủ số lượng mỗi màu. Pattern have/need mở rộng trực tiếp sang những bài đó.

Bài liên quan

Permutation in String (567) — fixed-size window, cùng have/need counter. Kích thước window là len(p), vậy chỉ di chuyển left khi right - left + 1 > len(p). Đơn giản hơn bài 76 vì không cần minimize; dừng ngay khi have == required.

Find All Anagrams in a String (438) — cùng fixed-size window như 567, nhưng thay vì dừng ở match đầu tiên thì thu thập tất cả starting index mà have == required. Cùng counter, khác output.

Longest Substring Without Repeating Characters (3) — variable window, không cần frequency map. Constraint hợp lệ là "không có ký tự nào xuất hiện nhiều hơn một lần", duy trì bằng set. Thu nhỏ khi ký tự đến đã tồn tại trong window.

Minimum Size Subarray Sum (209) — variable window trên mảng số nguyên với sum constraint thay vì frequency constraint. Điều kiện shrink khác nhưng cấu trúc vòng lặp expand-then-shrink hoàn toàn giống.