Longest Repeating Character Replacement

Bài toán

Cho một chuỗi s chỉ gồm chữ cái in hoa và một số nguyên k. Bạn được phép thay thế tối đa k ký tự bất kỳ trong chuỗi thành bất kỳ ký tự nào khác. Hãy tìm độ dài của chuỗi con dài nhất chứa toàn bộ các ký tự giống nhau sau khi thực hiện thay thế.

Ví dụ:

Input: s = "ABAB", k = 2
Output: 4
Giải thích: Thay 2 chữ 'A' thành 'B' -> "BBBB". Độ dài 4.

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

Điều kiện hợp lệ của cửa sổ

Giả sử ta xét cửa sổ substring. Làm sao biết nó có thể biến thành chuỗi đồng nhất với tối đa k lần sửa? Ta cần giữ lại ký tự xuất hiện nhiều nhất (Most Frequent Character) và sửa tất cả các ký tự còn lại. Số lượng ký tự cần sửa = (Độ dài cửa sổ) - (Tần suất của ký tự phổ biến nhất).

Nếu (Length - MaxFreq) <= k: Cửa sổ hợp lệ. Nếu (Length - MaxFreq) > k: Không đủ quyền sửa đổi k lần để biến cửa sổ này thành đồng nhất. Cần thu hẹp.

Thuật toán Sliding Window

1. Duyệt right để mở rộng cửa sổ.
2. Cập nhật tần suất ký tự mới vào Hash Map (hoặc mảng 26).
3. Cập nhật maxF (Tần suất lớn nhất lịch sử trong cửa sổ hiện tại).
4. Kiểm tra điều kiện: WindowLen - maxF > k.
   • Nếu sai (vi phạm): Thu hẹp cửa sổ (left++). Giảm tần suất ký tự bị loại bỏ.
5. Cập nhật kết quả maxLen.

function characterReplacement(s: string, k: number): number {
    const count: Record<string, number> = {};
    let l = 0;
    let maxF = 0; // Tần suất của ký tự phổ biến nhất trong cửa sổ
    let res = 0;

    for (let r = 0; r < s.length; r++) {
        // Cập nhật count
        count[s[r]] = (count[s[r]] || 0) + 1;
        
        // Cập nhật max frequency
        // Mẹo: Ta không cần tìm global max freq, chỉ cần biết maxF trong lịch sử
        // lớn nhất có thể giúp cửa sổ mở rộng. Nếu maxF giảm, cửa sổ cũng không thể mở rộng hơn kỷ lục cũ.
        maxF = Math.max(maxF, count[s[r]]);

        // Kiểm tra điều kiện: Có đủ k để bù đắp cho phần còn lại không?
        // (r - l + 1) là độ dài cửa sổ
        while ((r - l + 1) - maxF > k) {
            count[s[l]]--; // Loại bỏ ký tự bên trái
            l++;
        }

        res = Math.max(res, r - l + 1);
    }

    return res;
}

• Time Complexity: $O(n)$ - Mặc dù có vẻ ta cần tìm max của map mỗi lần, nhưng nhờ mẹo tối ưu biến maxF, ta không cần duyệt Map (với bảng chữ cái 26 ký tự thì duyệt map cũng coi là O(1) hoặc O(26)).
• Space Complexity: $O(26) = O(1)$ để lưu tần suất.

Mẹo tối ưu (Advanced Trick)

Trong đoạn code trên, while có thể được thay bằng if. Tại sao? Vì ta chỉ quan tâm tìm độ dài LỚN NHẤT. Khi cửa sổ bị vi phạm (len - maxF > k), ta chỉ cần dịch chuyển cả cửa sổ sang phải (l++, r++ ở vòng lặp sau) thay vì co nó lại. Bởi vì co nhỏ lại thì chắc chắn độ dài sẽ bé hơn kỷ lục hiện tại (res), ta không cần tính nó làm gì. Ta chỉ cần cửa sổ hợp lệ khi nó có tiềm năng phá vỡ kỷ lục.

Tuy nhiên, dùng while như trên là dễ hiểu và chuẩn mực nhất cho mọi bài Sliding Window.