Longest Repeating Character Replacement ใน C++

ตัวอย่าง: s = "ABAB", k = 2

เปลี่ยน 2 ตัว 'B' → 'A' ได้ "AAAA" ความยาว 4 → ผลลัพธ์: 4

อัลกอริทึม: Sliding Window + Character Count

รักษาหน้าต่าง [left, right] ที่เป็น "valid" = สามารถเปลี่ยนตัวอักษรในหน้าต่างให้เหมือนกันทั้งหมดได้ภายใน k ครั้ง

เงื่อนไข valid: window_size - max_frequency_in_window <= k

(จำนวนตัวที่ต้องเปลี่ยน = ขนาดหน้าต่าง - จำนวนตัวอักษรที่พบบ่อยที่สุดในหน้าต่าง)

1. maxCount = 0, ans = 0, left = 0
2. count[26] = {0} นับความถี่ในหน้าต่างปัจจุบัน
3. วน right = 0..n-1 (ขยายขวา):
   • count[s[right]-'A']++
   • maxCount = max(maxCount, count[s[right]-'A'])
   • ในขณะที่ (right - left + 1) - maxCount > k (invalid):
     • count[s[left]-'A']-- (หดซ้าย)
     • left++
   • ans = max(ans, right - left + 1)
4. ส่งคืน ans

จุดสำคัญ: maxCount ไม่ต้องลดลงเมื่อหดหน้าต่างซ้าย เพราะเราหา ค่าสูงสุดที่เคยเจอ** ไม่ใช่ค่าปัจจุบันในหน้าต่าง การที่ maxCount เก่ากว่าจริง ทำให้เงื่อนไข strict กว่า แต่ก็ยังถูกต้อง (อาจพลาดคำตอบที่ดีกว่าเล็กน้อยแต่ในทางปฏิบัติถูกต้องเสมอ)

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

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> count(26, 0);
        int maxCount = 0;
        int ans = 0;
        int left = 0;
        
        for (int right = 0; right < s.size(); right++) {
            count[s[right] - 'A']++;
            maxCount = max(maxCount, count[s[right] - 'A']);
            
            // หน้าต่างไม่ valid: ต้องเปลี่ยนมากกว่า k ตัว
            while (right - left + 1 - maxCount > k) {
                count[s[left] - 'A']--;
                left++;
            }
            
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

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

"ABAB" 2

4