Day22力扣打卡

打卡记录

替换子串得到平衡字符串（滑动窗口）

链接

由于是以后统计替换的子串，不可以直接使用hash表统计的每个次数大于 n / 4 的字符，再将其次数减去平衡数来得到答案，根据字符串的连贯性，使用 滑动窗口 来进行求解。

class Solution {
public:
    int balancedString(string s) {
        int n = s.length(), m = n / 4, cnt['X']{};
        for (char c : s) ++cnt[c];
        if (cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m) return 0;
        int ans = n, left = 0;
        for (int right = 0; right < n; right++) {
            --cnt[s[right]];
            while (cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m) {
                ans = min(ans, right - left + 1);
                ++cnt[s[left++]];
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17