Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/longest-repeating-character-replacement/description/
Table of Contents
1. Cách tiếp cận vấn đề
Đề bài: Cho chuỗi s chỉ gồm các chữ cái viết hoa (A–Z) và một số nguyên k. Bạn được phép thay đổi tối đa k ký tự bất kỳ thành ký tự khác (cũng là A–Z). Yêu cầu tìm độ dài lớn nhất của một substring sao cho sau khi hoàn thành tối đa k phép thay đổi, substring đó phải chứa toàn các ký tự giống nhau.
Ví dụ:
- Input: s = "AABABBA", k = 1
- Output: 4
- Explanation: Thay thế ký tự 'A' thành ký tự 'B' ta thu được chuỗi "AABBBBA". Chuỗi "BBBB" với 4 ký tự, trở thành chuỗi con dài nhất chỉ chứa các ký tự trùng lặp.
- Note: Bài toán còn có thể có nhiều cách khác để đạt được cùng đáp án 4, ví dụ như thay ký tự 'B' thành 'A' để thu được chuỗi "AAAABBA".
Giả sử ta có trong tay 1 substring s nào đó, tạm gọi là s có chiều dài là s_len, thì trong s luôn luôn sẽ có 1 ký tự xuất hiện maxCount lần - nhiều hơn hoặc bằng các ký tự còn lại, mục tiêu của chúng ta sẽ là dùng tối đa k lần để biến đổi những ký tự còn lại đó.
- Nếu s_len - maxCount ≤ k, tức là ta có thể "cover" các ký tự khác bằng việc thay đổi, thì substring hiện tại hợp lệ.
- Còn nếu vượt quá k, ta phải thu nhỏ substring về từ bên trái.
Vì chiều dài s có thể rất lớn (10^5), ta cần một giải pháp hiệu quả O(n) chứ không thể brute-force kiểm mọi substring.
2. Solution & Phân Tích
Kỹ thuật sliding windows là thứ mà mình nghĩ đến đầu tiên đối với những bài dạng substring như thế này.
- Ta sẽ sử dụng 2 con trỏ left (bắt đầu cửa sổ) và right (kết thúc cửa sổ).
- Mảng count[26] để đếm tần suất xuất hiện của 26 ký tự tương ứng trong cửa sổ hiện tại.
- Biến maxCount giữ số lần xuất hiện nhiều nhất của một ký tự trong cửa sổ hiện tại (hoặc từng thấy, mình sẽ giải thích thêm ý này sau)
- Mỗi khi mở rộng cửa sổ (right++), thì:
- Cập nhật lại count[c] cho ký tự c = s[right];
- Cập nhật lại maxCount = max(maxCount, count[c])
- Tính windowSize = right - left + 1. Nếu windowSize - maxCount > k, nghĩa là cần thay thế quá nhiều ký tự -> thu nhỏ window: giảm counts[s[left]]-- và left++
- Cập nhật kết quả maxLen = max(maxLen, windowSize) nếu window hợp lệ.
- Cuối cùng, trả về maxLen
Nếu ký tự left bị loại bỏ chính là ký tự đang xuất hiện nhiều nhất trong cửa sổ hiện tại thì cập nhật lại giá trị maxCount như thế nào cho hiệu quả? -> Nếu loop lại từ left đến right để tìm và cập nhật lại maxCount thì sẽ rất tốn kém.
Chính vì vậy ta nên xem maxCount là giá trị lớn nhất từng thấy, và chỉ cập nhật lại nó mỗi khi có giá trị lớn hơn nó, chứ không cần làm nó khớp với cửa sổ đang duyệt hiện tại. Cách này vẫn đúng mà vẫn đảm bảo ta không bỏ lỡ cửa sổ hợp lệ lớn nhất và tránh việc tính lại maxCount nhiều lần gây tốn chi phí. Mình sẽ chứng minh bằng vài lập luận ngắn gọn như sau:
- Giả sử số lần xuất hiện lớn nhất từng thấy maxCount = X, thì lúc đó maxLen sẽ bằng X + k = kích thước của cửa sổ hợp lệ lúc đó. NOTE: từng thấy có nghĩa là bắt buộc cửa sổ windows phải vi phạm và cần tìm cửa sổ mới, tránh các case như: "AAAA" và k là số bất kỳ; hay "AAAB" và k = 2 (chung quy là k chưa được dùng hết)
- Và để tìm được cửa sổ hợp lệ lớn hơn, chắc chắn giá trị maxCount phải được cập nhật, vì k thì luôn không đổi.
- Mà để cập nhật được maxCount, thì chắc chắn ta phải phát hiện được ký tự đó trong những lần mở rộng cửa sổ (right++). Hay nói cách khác, là ta sẽ không bao giờ bỏ lỡ việc cập nhật maxCount.
- Nếu không cập nhật được maxCount, thì sẽ tăng left, và đảm bảo cửa sổ sẽ luôn được duy trì với giá trị maxLen
Time-Complexity: O(n) vì khi right chạy một vòng, left cũng chỉ tăng tối đa n lần.
Space-Complexity: O(1) vì mảng count cố định kích thước là 26 và không phụ thuộc vào n.3. Code
