Mô phỏng thuật toán Chuỗi con nhiều nhất K ký tự khác nhau

Longest Substring with K Distinct · Nhóm: Cửa sổ trượt

Tìm chuỗi con DÀI NHẤT của s có nhiều nhất K ký tự phân biệt, bằng cửa sổ trượt và bảng tần suất.

Ý tưởng

Mở con trỏ phải R nạp thêm ký tự vào bảng tần suất; số khóa của bảng chính là số ký tự khác nhau trong cửa sổ.

Khi số ký tự khác nhau vượt K thì co con trỏ trái L, giảm tần suất và bỏ khóa về 0, cho tới khi trở lại ≤ K; ghi lại cửa sổ dài nhất.

Vì sao đúng

Cả L và R chỉ tiến một chiều nên mỗi ký tự vào ra cửa sổ tối đa một lần, tổng O(n); dùng bảng băm để đếm số ký tự phân biệt trong O(1) trung bình cho mỗi bước.

Mã Python

def longest_k_distinct(s, k):
    freq = {}
    L = 0; best = (0, -1)
    for R, c in enumerate(s):
        freq[c] = freq.get(c, 0) + 1
        while len(freq) > k:
            freq[s[L]] -= 1
            if freq[s[L]] == 0: del freq[s[L]]
            L += 1
        if R - L > best[1] - best[0]:
            best = (L, R)
    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.