Mô phỏng thuật toán Thay ký tự cho đoạn đồng nhất dài nhất

Longest Repeating Char Replacement · Nhóm: Cửa sổ trượt

Tìm đoạn con DÀI NHẤT mà chỉ cần đổi nhiều nhất K ký tự là cả đoạn giống nhau, bằng cửa sổ trượt giữ tần suất ký tự trội.

Ý tưởng

Mở con trỏ phải R nạp ký tự vào bảng tần suất; số ký tự cần đổi để đoạn đồng nhất = độ dài cửa sổ trừ số lần xuất hiện của ký tự trội.

Khi số ký tự cần đổi vượt K thì co con trỏ trái L cho tới khi hợp lệ trở lại; ghi lại cửa sổ dài nhất từng thấy.

Vì sao đúng

L và R chỉ tiến một chiều nên tổng O(n); cửa sổ hợp lệ khi (độ dài − tần suất trội) ≤ K, nghĩa là số ký tự khác ký tự trội đủ ít để thay hết trong K lần đổi.

Mã Python

def char_replace(s, k):
    freq = {}
    L = 0; best = 0
    for R, c in enumerate(s):
        freq[c] = freq.get(c, 0) + 1
        max_freq = max(freq.values())
        while (R - L + 1) - max_freq > k:
            freq[s[L]] -= 1
            L += 1
            max_freq = max(freq.values())
        best = max(best, R - L + 1)
    return best

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