แทนที่สตริงย่อยเพื่อทำให้สตริงสมดุลใน C++

ให้สตริงที่ประกอบด้วยตัวอักษร 4 ตัวคือ 'Q', 'W', 'E', 'R' สตริงจะ สมดุล (balanced) ถ้าแต่ละตัวอักษรปรากฏเท่ากัน n/4 ครั้ง (n = ความยาวสตริง) ต้องการหาความยาวน้อยที่สุดของสตริงย่อยที่สามารถแทนที่ได้เพื่อทำให้สตริงทั้งหมดสมดุล หากสมดุลอยู่แล้ว คืน 0

ตัวอย่าง: s = "QQWE" → คำตอบ 1 (แทน Q ด้วย R ได้ "RQWE")

ขั้นตอนการแก้ปัญหา (Sliding Window)

1. นับความถี่ตัวอักษรทั้งหมดใน m, n = s.size()
2. res = n, left = 0
3. วน right จาก 0 ถึง n-1:
   • ลดความถี่ s[right] ใน m
   • พร้อมที่ m['Q'] <= n/4 && m['W'] <= n/4 && m['E'] <= n/4 && m['R'] <= n/4:
     • res = min(res, right - left + 1)
     • เพิ่มความถี่ s[left] กลับ, left++
4. คืน res

ไอเดีย: หาช่วงสั้นที่สุดที่ถ้าตัดออก (หรือแทนที่) ตัวอักษรที่เหลือจะไม่เกินโควต้า n/4

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

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

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

int main() {
    Solution ob;
    cout << ob.balancedString("QQEQ");
}

Input

"QQEQ"

Output

2