1234.replace-the-substring-for-balanced-string 替换子串得到平衡字符串

问题描述

1234.替换子串得到平衡字符串

解题思路

利用两个指针left，right，right从0开始遍历，如果[left, right]之外的字符串中，每个字符出现次数都小于或等于n / 4，说明替换[left, right]可以构成平衡字符串，此时递增left，直到移除[left, right]不能构成平衡字符串。

代码

class Solution {
public:
    bool check(unordered_map<char, int> &mp, int m) {
        if (mp['Q'] > m || mp['W'] > m || mp['E'] > m || mp['R'] > m)
            return true;
        else
            return false;
    }
    int balancedString(string s) {
        int n = s.size(), partial = n / 4;
        int res = n;
        unordered_map<char, int> chars;
        for (auto &c : s)
            chars[c]++;
        int flag = 1;
        for (auto &pa : chars) { // 检查字符串本身是否平衡
            if (pa.second != partial)
                flag = 0;
        }
        if (flag == 1)
            return 0;
        for (int right = 0, left = 0; right < n; right++) {
            chars[s[right]]--;
            while (left <= right && !check(chars, partial)) {
                chars[s[left]]++;
                res = min(right - left + 1, res);
                left++;  
            }

        }
        return res;
    }
};