Swap เพื่อหา Substring ตัวอักษรซ้ำยาวที่สุดใน C++

ปัญหา

ให้ String Text สลับตัวอักษร 2 ตัวได้ 1 ครั้ง หาความยาว Substring ที่ตัวอักษรซ้ำกันติดกันยาวที่สุด

ตัวอย่าง: "ababa" → สลับ b แรกกับ a ท้าย → "aaabb" → "aaa" ยาว 3

อัลกอริทึม (Sliding Window + Frequency Map)

1. นับ Frequency ของทุกตัวอักษรใน String (Map m)
2. Sliding Window [j, i] รักษาเงื่อนไข: ใน Window มีตัวอักษรที่ซ้ำได้สูงสุด 2 ตัว
3. ถ้าเกิน 2 ตัว → ยุบ Window ด้านซ้าย (j++)
4. สำหรับ Window ที่ถูกต้อง: ตรวจสอบว่าสามารถขยายได้ด้วยการ Swap (มีตัวอักษรนอก Window เหลืออยู่)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int maxRepOpt1(string text) {
        int n = text.size();
        map<char, int> total_freq;
        for (char c : text) total_freq[c]++;
        
        map<char, int> window_freq;
        set<char> window_chars;
        int j = 0, ans = 1;
        
        for (int i = 0; i < n; i++) {
            window_freq[text[i]]++;
            window_chars.insert(text[i]);
            
            // ยุบ window ถ้ามี distinct chars > 2
            while (window_chars.size() > 2) {
                window_freq[text[j]]--;
                if (window_freq[text[j]] == 0) 
                    window_chars.erase(text[j]);
                j++;
            }
            
            // หาตัวอักษรที่มากที่สุดใน window
            char major = text[i];
            for (char c : window_chars)
                if (window_freq[c] > window_freq[major])
                    major = c;
            
            // เช็คว่าสามารถขยายได้ด้วย swap หรือไม่
            int window_len = i - j + 1;
            int available_outside = total_freq[major] - window_freq[major];
            
            if (window_chars.size() == 1 || available_outside > 0)
                ans = max(ans, window_len);
            else
                ans = max(ans, window_len - 1);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.maxRepOpt1("ababa") << endl; // 3
    cout << ob.maxRepOpt1("aaabaaa") << endl; // 6
    return 0;
}

ผลลัพธ์

3
6

คำอธิบาย "aaabaaa"

Total: a=6, b=1

Window "aaabaaa" (ทั้ง String) มี a=6, b=1 → major='a' available_outside=0

แต่ window_chars.size()=2 และ available_outside=0 → ans = 7-1 = 6

สลับ b กับ a นอก window (ไม่มี) → ตัด b ออก → "aaaaaa" = 6