Longest Repeating Character Replacement trong C++

Cho chuỗi s chỉ chứa chữ in hoa, cho phép tối đa k phép thay đổi ký tự (thay ký tự bất kỳ thành chữ in hoa khác). Tìm độ dài substring dài nhất chứa toàn ký tự giống nhau sau tối đa k thay đổi.

Ví dụ: s="ABAB", k=2 → output 4 (thay 2 'A' thành 'B' hoặc ngược lại).

Giải thuật (Sliding Window)

• maxCount=0, ans=0, cnt[26], j=0.
• Duyệt i=0..n-1:
  • cnt[s[i]-'A']++, cập nhật maxCount.
  • Khi i-j+1 - maxCount > k: thu hẹp cửa sổ (cnt[s[j]-'A']--, j++).
  • ans = max(ans, i-j+1).
• Trả về ans.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxCount = 0, ans = 0, n = s.size();
        vector<int> cnt(26);
        int j = 0;
        for (int i = 0; i < n; i++) {
            cnt[s[i]-'A']++;
            maxCount = max(maxCount, cnt[s[i]-'A']);
            while (j <= i && i - j + 1 - maxCount > k) {
                cnt[s[j]-'A']--;
                j++;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.characterReplacement("ABAB", 2);
    return 0;
}

Input

"ABAB" 2

Output

4