Thay thế chuỗi con để cân bằng chuỗi trong C++

Mô tả bài toán

Cho chuỗi chỉ chứa 'Q','W','E','R'. Chuỗi cân bằng khi mỗi ký tự xuất hiện đúng n/4 lần. Tìm độ dài nhỏ nhất của chuỗi con có thể thay thế để chuỗi trở thành cân bằng.

Ví dụ: "QQWE" → 1 (thay 'Q' bằng 'R' thành "RQWE").

Giải thuật Cửa sổ trượt (Sliding Window)

1. Đếm tần suất từng ký tự trong toàn chuỗi.
2. Mục tiêu: tìm cửa sổ nhỏ nhất sao cho khi loại bỏ nó, các ký tự còn lại đều ≤ n/4.
3. Duyệt right từ 0 đến n-1, giảm count của s[right].
4. Khi cửa sổ hiện tại thỏa mãn (tất cả count ≤ n/4), thu hẹp từ trái (left++) và cập nhật kết quả.

Cài đặt C++

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

class Solution {
public:
    int balancedString(string s) {
        unordered_map<char, int> cnt;
        for (char c : s) cnt[c]++;
        int n = s.size(), target = n / 4;
        int res = n, left = 0;
        for (int right = 0; right < n; right++) {
            cnt[s[right]]--;
            while (left < n && cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target) {
                res = min(res, right - left + 1);
                cnt[s[left++]]++;
            }
        }
        return res;
    }
};

int main() {
    Solution ob;
    cout << ob.balancedString("QQEQ"); // 2
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1) (chỉ 4 ký tự).