Minimum Window Substring

Độ Khó: Hard

Bài toán

Cho hai chuỗi s và t. Tìm chuỗi con nhỏ nhất (minimum window substring) của s sao cho nó chứa tất cả các ký tự của t (bao gồm cả số lượng lặp lại). Nếu không có, trả về chuỗi rỗng.

Ví dụ:

text:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Giải thích: "BANC" chứa A, B, C. Độ dài 4 là nhỏ nhất có thể.

Phân Tích & Tiếp Cận

Logic Cốt Lõi

Mở rộng (right): Thêm ký tự vào cửa sổ cho đến khi cửa sổ hợp lệ (chứa đủ mọi ký tự của t).
Thu hẹp (left): Khi cửa sổ đã hợp lệ, ta cố gắng thu hẹp nó từ bên trái để tìm ra kích thước nhỏ nhất mà vẫn giữ được tính hợp lệ.
Lặp lại quá trình.

Cách kiểm tra "Hợp lệ" hiệu quả

Thay vì so sánh hai Hash Map mỗi lần (tốn thời gian), ta dùng biến đếm have và need.

countT: Hash Map tần suất ký tự của t.
window: Hash Map tần suất ký tự hiện tại trong cửa sổ.
have: Số lượng ký tự độc nhất (unique char) đã thỏa mãn yêu cầu. (Ví dụ t="AABC", ta cần thỏa mãn A(2), B(1), C(1). Nếu cửa sổ có AA thì have tăng 1 cho A).
need: Tổng số ký tự độc nhất trong t (Keys của countT).

Khi have == need -> Cửa sổ hợp lệ.

typescript:

function minWindow(s: string, t: string): string {
    if (t === "") return "";

    const countT: Record<string, number> = {};
    const window: Record<string, number> = {};

    // 1. Tạo frequency map cho t
    for (const c of t) {
        countT[c] = (countT[c] || 0) + 1;
    }

    let have = 0;
    let need = Object.keys(countT).length;
    
    let res: [number, number] = [-1, -1];
    let resLen = Infinity;

    let l = 0;

    for (let r = 0; r < s.length; r++) {
        const char = s[r];
        window[char] = (window[char] || 0) + 1;

        // Nếu số lượng ký tự này trong cửa sổ khớp với yêu cầu của t
        if (countT[char] && window[char] === countT[char]) {
            have++;
        }

        // Khi cửa sổ đã hợp lệ, cố gắng thu hẹp từ bên trái
        while (have === need) {
            // Cập nhật kết quả nếu tìm thấy chuỗi nhỏ hơn
            if ((r - l + 1) < resLen) {
                resLen = r - l + 1;
                res = [l, r];
            }

            // Pop ký tự bên trái
            const leftChar = s[l];
            window[leftChar]--;
            
            // Nếu việc pop này làm mất tính hợp lệ
            if (countT[leftChar] && window[leftChar] < countT[leftChar]) {
                have--;
            }
            l++;
        }
    }

    return resLen === Infinity ? "" : s.substring(res[0], res[0] + resLen);
}

Time Complexity: $O(n)$ - Tuy có vòng lặp lồng nhau, nhưng mỗi ký tự left và right chỉ chạy từ 0 đến n đúng 1 lần.
Space Complexity: $O(1)$ (vì Map chỉ chứa tối đa 52 ký tự hoa thường).

Pattern Nhận Diện

Đây là bài toán khuôn mẫu cho dạng "Dynamic Sliding Window with Validity Check":

Expand until Valid.
Shrink while Valid (to find minimum).

Đây cũng là một trong những bài phỏng vấn phổ biến nhất tại Facebook và Google.

Bài trước

Valid Palindrome

Bài tiếp theo

Longest Repeating Character Replacement