Description Link to heading

1234.replace-the-substring-for-balanced-string

Solution Link to heading

We use two pointers left and right. Let’s traverse the string throughright from right = 0. If the amount of each character in the string other than [left, right] is less than or equal to n / 4, it means that we can form a balanced string by replacing [left, right], then increment left until [left, right] can’t form a balanced string.

Code Link to heading 

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;
    }
};