Longest Repeating Character Replacement: trick kiểm tra tính hợp lệ của cửa sổ

Điều kiện để kiểm tra tính hợp lệ của bài toán này gói gọn trong một dòng: (window_size - max_freq) <= k. Nếu số ký tự cần thay thế để làm window trở nên đồng nhất vượt quá ngân sách k, window đó không hợp lệ. Mọi thứ còn lại — two pointers, frequency map, vòng lặp ngoài — chỉ là cơ chế để duy trì điều kiện bất biến đó trong khi đẩy window dài nhất có thể.

Phần tinh tế nằm ở ý nghĩa của max_freq và tại sao bạn có thể để nó không hoàn toàn chính xác.

Bài toán thực sự đang hỏi gì

Bạn có một chuỗi chữ hoa và ngân sách k lần thay thế. Bạn muốn tìm substring liên tiếp dài nhất mà sau khi dùng tối đa k lần thay thế, tất cả ký tự đều giống nhau.

Chiến lược tối ưu bên trong bất kỳ window nào là hiển nhiên: giữ nguyên ký tự xuất hiện nhiều nhất, thay thế tất cả phần còn lại. Vậy chi phí để làm một window đồng nhất là window_size - count_of_most_frequent_character. Điều kiện ràng buộc là chi phí này không được vượt quá k.

Đó là toàn bộ bài toán, được phát biểu lại dưới dạng bất đẳng thức: (right - left + 1) - max_freq <= k.

Constraints nói gì

1 <= s.length <= 10^5 loại ngay O(n²) và chắc chắn O(n³). Cần O(n). Chuỗi chỉ gồm chữ hoa tiếng Anh — giới hạn frequency map ở tối đa 26 entries, nên space thực tế là O(1) bất kể thuật toán. k có thể là 0 (không được thay thế) hoặc lớn bằng s.length (thay thế toàn bộ chuỗi), vậy cả hai cực đoan đều phải hoạt động đúng mà không cần xử lý đặc biệt.

Bảng chữ cái 26 ký tự là món quà thầm lặng. Chỉ có 26 giá trị khác nhau nên mọi thao tác trên frequency map tốn O(26) = O(1). Không lo hash collision. Đây cũng chính là lý do brute force O(n²) thắng O(n³) khi tái sử dụng map thay vì xây lại từ đầu — và sliding window đẩy ý tưởng tái sử dụng đó đến giới hạn tự nhiên của nó.

Brute force O(n³): duyệt toàn bộ substring

Điểm khởi đầu rõ ràng nhất là kiểm tra mọi cặp (i, j). Với mỗi window, xây frequency map từ đầu, tìm ký tự phổ biến nhất, tính chi phí thay thế, và cập nhật kết quả nếu chi phí nằm trong k.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_length = 0
        n = len(s)
        for i in range(n):
            for j in range(i, n):
                char_count = {}
                for idx in range(i, j + 1):
                    char_count[s[idx]] = char_count.get(s[idx], 0) + 1
                max_freq = max(char_count.values())
                if (j - i + 1) - max_freq <= k:
                    max_length = max(max_length, j - i + 1)
        return max_length

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int maxLength = 0;
        int n = s.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                var charCount = new Dictionary<char, int>();
                for (int idx = i; idx <= j; idx++) {
                    charCount[s[idx]] = charCount.GetValueOrDefault(s[idx], 0) + 1;
                }
                int maxFreq = charCount.Values.Max();
                if ((j - i + 1) - maxFreq <= k)
                    maxLength = Math.Max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}

O(n³) time, O(1) space (tối đa 26 entries trong map). Bị time-limit-exceeded ở n = 10^5. Nhưng nó làm điều kiện hợp lệ trở nên cụ thể: (j - i + 1) - max_freq <= k là toàn bộ phép kiểm tra. Mọi approach sau đều giữ nguyên đúng điều kiện này.

Brute force O(n²): frequency map tăng dần

Cố định i và mở rộng j từng bước, cập nhật count cho s[j] thay vì xây lại từ đầu. Thân vòng lặp trong co từ O(n) xuống O(1), kéo toàn bộ xuống O(n²).

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_length = 0
        n = len(s)
        for i in range(n):
            char_count = {}
            for j in range(i, n):
                char_count[s[j]] = char_count.get(s[j], 0) + 1
                max_freq = max(char_count.values())
                if (j - i + 1) - max_freq <= k:
                    max_length = max(max_length, j - i + 1)
        return max_length

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int maxLength = 0;
        for (int i = 0; i < s.Length; i++) {
            var charCount = new Dictionary<char, int>();
            for (int j = i; j < s.Length; j++) {
                charCount[s[j]] = charCount.GetValueOrDefault(s[j], 0) + 1;
                int maxFreq = charCount.Values.Max();
                if ((j - i + 1) - maxFreq <= k)
                    maxLength = Math.Max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}

O(n²) time (lệnh Max() là O(26) = O(1) vì alphabet cố định), O(1) space. Vẫn quá chậm ở n = 10^5, nhưng nó lộ ra vấn đề cần sửa: khi i tiến lên, ta vứt bỏ toàn bộ frequency map và bắt đầu lại. Sliding window sửa điều đó.

Walkthrough nhanh trên s = "ABAB", k = 2:

• i=0, j=0: window "A", cost = 1 - 1 = 0 <= 2. Length 1.
• i=0, j=1: window "AB", max_freq('A')=1, cost = 2 - 1 = 1 <= 2. Length 2.
• i=0, j=2: window "ABA", max_freq('A')=2, cost = 3 - 2 = 1 <= 2. Length 3.
• i=0, j=3: window "ABAB", max_freq=2, cost = 4 - 2 = 2 <= 2. Length 4. Kết quả.

Sliding window: O(n)

Thay vì bắt đầu lại từ mỗi i, duy trì một window duy nhất với hai con trỏ. Khi right tiến, chỉ cập nhật count cho s[right]. Khi window không hợp lệ, tiến left một bước và cập nhật count cho s[left]. Frequency map duy trì tính chính xác xuyên suốt và không bao giờ bị xây lại.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        char_count = {}
        left = 0
        max_freq = 0
        max_length = 0
 
        for right in range(len(s)):
            char_count[s[right]] = char_count.get(s[right], 0) + 1
            max_freq = max(max_freq, char_count[s[right]])
 
            if (right - left + 1) - max_freq > k:
                char_count[s[left]] -= 1
                left += 1
 
            max_length = max(max_length, right - left + 1)
 
        return max_length

public class Solution {
    public int CharacterReplacement(string s, int k) {
        var charCount = new Dictionary<char, int>();
        int left = 0, maxFreq = 0, maxLength = 0;
 
        for (int right = 0; right < s.Length; right++) {
            charCount[s[right]] = charCount.GetValueOrDefault(s[right], 0) + 1;
            maxFreq = Math.Max(maxFreq, charCount[s[right]]);
 
            if ((right - left + 1) - maxFreq > k) {
                charCount[s[left]]--;
                left++;
            }
 
            maxLength = Math.Max(maxLength, right - left + 1);
        }
 
        return maxLength;
    }
}

O(n) time, O(1) space. Mỗi ký tự được thêm vào một lần và bị loại bỏ nhiều nhất một lần.

Trace tay trên "AABABBA", k = 1

Đây là ví dụ từ đề bài. Đi qua từng bước là cách nhanh nhất để thấy tại sao max_freq không cần hoàn toàn chính xác.

Sơ đồ trên hiển thị window ở kích thước tối đa (right=3, left=0, size=4). Bảng trạng thái:

right=0  s[r]='A'  count={A:1}        max_freq=1  size=1  cost=0  hop le
right=1  s[r]='A'  count={A:2}        max_freq=2  size=2  cost=0  hop le
right=2  s[r]='B'  count={A:2,B:1}   max_freq=2  size=3  cost=1  hop le
right=3  s[r]='A'  count={A:3,B:1}   max_freq=3  size=4  cost=1  hop le
right=4  s[r]='B'  count={A:3,B:2}   max_freq=3  size=5  cost=2  KHONG HOP LE
         loai s[left=0]='A' -> count={A:2,B:2}, left=1, max_freq giu nguyen 3
         window size=4
right=5  s[r]='B'  count={A:2,B:3}   max_freq=3  size=5  cost=2  KHONG HOP LE
         loai s[left=1]='A' -> count={A:1,B:3}, left=2, max_freq giu nguyen 3
         window size=4
right=6  s[r]='A'  count={A:2,B:3}   max_freq=3  size=5  cost=2  KHONG HOP LE
         loai s[left=2]='B' -> count={A:2,B:2}, left=3, max_freq giu nguyen 3
         window size=4

Ket qua: 4

Window đạt kích thước 4 tại right=3 và không bao giờ vượt qua được. Từ right=4 trở đi, left đi song song với right cách một bước, giữ window cố định ở 4. max_freq giữ nguyên ở 3 suốt — đúng, vì ta không quan tâm window hiện tại có thực sự đạt tần suất 3 không, mà hỏi rằng window kích thước 5 nào đó trong tương lai có thể đạt không. Đã có rồi, nên ngưỡng được đặt.

Hai lựa chọn phản trực giác trong solution tối ưu

Tại sao left di chuyển đúng một bước, không phải cho đến khi hợp lệ. Khi (right - left + 1) - max_freq > k, bạn có thể kỳ vọng vòng lặp while: tiếp tục thu nhỏ cho đến khi window hợp lệ trở lại. Code chỉ làm một left += 1. Điều này đúng vì ta đang tìm window dài nhất từng thấy, không phải chỉ window hợp lệ dài nhất hiện tại. Nếu window kích thước L vừa không hợp lệ, thu nhỏ xuống L-1 rồi mở rộng thêm một bước giữ kích thước ở L. Không có lý do gì xem xét bất cứ thứ gì ngắn hơn L. Window vì vậy đơn điệu không giảm về kích thước.

Tại sao max_freq được phép không chính xác. Sau khi loại bỏ s[left], max_freq không giảm — dù ký tự bị loại là ký tự phổ biến nhất. Điều này có vẻ sai. Nếu bạn loại 'A' khi 'A' có tần suất 5, max_freq vẫn giữ 5 dù thực tế có thể là 4. Hoàn toàn ổn vì lý luận window đơn điệu ở trên: max_freq đại diện cho tần suất tốt nhất từng thấy trong lịch sử window. Kiểm tra hợp lệ dùng giá trị lịch sử này để quyết định giữ hay tăng kích thước window. Kết quả tại mỗi bước — right - left + 1 — là một window hợp lệ hoặc đúng bằng kích thước window hợp lệ tốt nhất từng thấy.

Bảng so sánh complexity

Space là O(1) cho cả ba vì alphabet cố định ở 26 chữ hoa — frequency map không bao giờ giữ quá 26 entries.

Edge cases

k = 0 — không được thay thế. Kết quả là độ dài run dài nhất của một ký tự lặp lại liên tiếp trong chuỗi gốc. Sliding window xử lý đúng: bất kỳ window nào có từ hai ký tự khác nhau trở lên lập tức vi phạm (size - max_freq) > 0, nên left bắt kịp và window chỉ giữ được run đồng nhất.

k >= s.length — có thể thay thế toàn bộ chuỗi. Kết quả luôn là s.length. Điều kiện hợp lệ luôn thỏa mãn và window phát triển đến hết chuỗi, không cần case đặc biệt.

Chuỗi đã đồng nhất — s = "AAAA", k = 2. max_freq bằng window_size xuyên suốt. Điều kiện vi phạm không bao giờ kích hoạt. Kết quả là s.length.

Chuỗi một ký tự — s = "A". Vòng lặp chạy một lần, left=0, right=0, max_length=1. Đúng.

k lớn hơn cần thiết — s = "ABCD", k = 10. Mọi window đều hợp lệ (thay thế 3 trong 4 ký tự tốn 3 <= 10). Window phát triển đến toàn bộ chuỗi và trả về 4.

Toàn ký tự khác nhau, k = 0 — s = "ABCDE", k = 0. Window không bao giờ giữ quá một ký tự. Kết quả là 1. max_freq giữ ở 1 xuyên suốt, và (size - 1) > 0 kích hoạt ngay khi size > 1.

Vị trí trong series sliding window

Bài này là bài thứ hai trong series sliding-window, ngay sau bài warmup fixed-window ở Best Time to Buy and Sell Stock. Ý tưởng mới cốt lõi ở đây là variable-size window: window có thể mở rộng hoặc giữ nguyên, và quyết định tại mỗi bước phụ thuộc vào điều kiện hợp lệ được duy trì bằng frequency map.

Điều kiện ở đây — window_size - max_freq <= k — là một trong những điều kiện rõ ràng nhất trong nhóm bài này. Đáng bỏ công hiểu kỹ vì cùng một shape tái xuất hiện:

Max Consecutive Ones III (1004) — cấu trúc giống hệt, binary array. k lần lật từ 0 sang 1. Điều kiện ánh xạ trực tiếp: (right - left + 1) - count_of_ones <= k. Làm ngay sau 424, chỉ mất vài phút.

Permutation in String (567) — fixed-size sliding window trên frequency vector 26 ký tự. Kiểm tra hợp lệ khác nhau (tất cả tần suất phải khớp target), nhưng cấu trúc expand-and-slide là cùng một pattern cơ học.

Minimum Window Substring (76) — giờ bạn muốn window ngắn nhất chứa tất cả ký tự của target. Bản năng dùng vòng lặp while là đúng ở đây: thu nhỏ càng nhiều càng tốt mỗi khi tìm được window hợp lệ. Làm sau 424 để thấy rõ sự tương phản giữa chiến lược window "dài nhất" và "ngắn nhất".

Longest Substring Without Repeating Characters (3) — variable-size window với điều kiện hợp lệ là "không có ký tự trùng lặp". Ràng buộc khác, cấu trúc giống nhau.

Tôi sẽ dùng sliding window cho bất kỳ hệ thống thực tế nào. O(n²) brute force hữu ích để kiểm tra logic với input nhỏ khi debug, nhưng ở n = 10^5 là 10^10 phép tính và đơn giản là không chạy xong. Sliding window không chỉ tốt hơn về mặt tiệm cận — nó là phần mở rộng tự nhiên của ý tưởng O(n²), chỉ đẩy thêm một bước: thay vì đặt lại map ở mỗi i mới, bạn mang nó theo và trừ đi ký tự ngoài cùng bên trái khi window cần thu nhỏ.