Mô phỏng thuật toán Cửa sổ nhỏ nhất chứa đủ ký tự

Minimum Window Substring · Nhóm: Cửa sổ trượt

Tìm cửa sổ con NGẮN NHẤT của chuỗi s chứa đủ mọi ký tự (kể cả số lần lặp) của chuỗi đích t, bằng cửa sổ trượt co giãn.

Ý tưởng

Đếm nhu cầu need[c] cho từng ký tự trong t; mở con trỏ phải R để nạp thêm ký tự cho tới khi cửa sổ phủ đủ mọi ký tự đích.

Khi đã đủ, co con trỏ trái L để bóp cửa sổ cho ngắn nhất mà vẫn hợp lệ; ghi lại cửa sổ tốt nhất, rồi tiếp tục mở R.

Vì sao đúng

Mỗi con trỏ L và R chỉ đi tiến qua chuỗi đúng một lần nên tổng thao tác là O(n); biến đếm missing cho biết cửa sổ đã đủ hay chưa trong O(1), tránh phải quét lại từng cửa sổ.

Mã Python

def min_window(s, t):
    need = Counter(t)
    missing = len(t)
    L = 0; best = (0, len(s) + 1)
    for R, c in enumerate(s):
        if need[c] > 0: missing -= 1
        need[c] -= 1
        while missing == 0:
            if R - L < best[1] - best[0]:
                best = (L, R)
            need[s[L]] += 1
            if need[s[L]] > 0: missing += 1
            L += 1
    return s[best[0]:best[1] + 1]

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.