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

798236606

传送门：https://leetcode-cn.com/problems ... or-balanced-string/

分析：
题目求子串的最小长度，首先考虑这样的子串符合什么样的条件？
答：对于每个多出来的字符种类，它在子串中的数量大于等于它多出来的数量。
比如：原字符串 = {Q : 3, W : 0, E: 4, R : 1}, len = 8。
显然，Q多了1个， E多了2个， 那么子字符串只要满足Q >= 1, E >= 2即可， 而最小的子字符串即为Q = 1, E == 2的情况。
为了方便检查子串是否符合条件，把每中字符的数量减去平衡数量，此时各个数量变成了相对数量， 其中大于0 的就是多余字符。

1.固定长度的滑动窗口

滑动窗口的长度从小到大遍历，对于每一长度的滑动窗口遍历一遍原字符串，一旦窗口内的子串条件符合，即为最小答案。

class Solution {
public:
    int balancedString(string s) {
        int hash['Z'];
        vector<int> cnt(4, 0);
        int n = s.size();

        hash['Q'] = 0;
        hash['W'] = 1;
        hash['E'] = 2;
        hash['R'] = 3;

        for (char c: s) ++cnt[hash[c]];//记录每个字母的数量

        for (int &i: cnt) i -= n / 4;

        int wd = 0;//代表滑动窗口的长度
        for (int i: cnt) if (i > 0) wd += i;//记录需要改变的字母数量，即为滑动窗口的起始长度

        if (!wd) return 0;

        for (; wd < n; ++wd)//滑动窗口的长度从小到大遍历，一旦条件符合，即为最小答案。
        {
            vector<int> now = cnt;
            
            for (int i = 0; i < n; ++i)//对于每个窗口，遍历一遍字符串
            {
                --now[hash[s[i]]];//减掉窗口最右边的字母

                if (i >= wd - 1)
                {
                    bool flag = true;

                    for (int j: now) if (j > 0) flag = false;

                    if (flag) return wd;//如果窗口内不再有字母数量大于零， 则符合条件

                    ++now[hash[s[i - wd + 1]]];//减掉窗口最左边的字母
                }
            }
        }

        return -1;
    }
};

2.双指针滑动窗口

定义r和l代表窗口的左右端，r先向右移探路，直到窗口符合条件，l再向右移试图使窗口更小。

class Solution {
public:
    int cnt[4] = {0};

    bool check(void)//检查是否符合条件
    {
        for (int i: cnt) if (i > 0) return false;

        return true;
    }

    int balancedString(string s) {
        int hash['Z'];
        hash['Q'] = 0;
        hash['W'] = 1;
        hash['E'] = 2;
        hash['R'] = 3;

        for (char c: s) ++cnt[hash[c]];

        int n = s.size();
        for (int &i: cnt) i -= n / 4;

        if (check()) return 0;
        
        int l = 0, r = 0, min_size = n;
        --cnt[hash[s[0]]];

        while (true)
        {
            if (check())//若窗口满足条件
            {
                min_size = min(min_size, r - l + 1);//更新最小窗口长度
                ++cnt[hash[s[l++]]];//窗口左端右移
            }
            else
            {
                if (r == n - 1) break;
                --cnt[hash[s[++r]]];//窗口右端右移
            }
        }

        return min_size;
    }
};

3.继续优化，发现其实r遍历了整个s的所有下标，不如直接遍历

class Solution {
public:
    int cnt[4] = {0};

    bool check(void)//检查是否符合条件
    {
        for (int i: cnt) if (i > 0) return false;

        return true;
    }

    int balancedString(string s) {
        int hash['Z'];
        hash['Q'] = 0;
        hash['W'] = 1;
        hash['E'] = 2;
        hash['R'] = 3;

        for (char c: s) ++cnt[hash[c]];

        int n = s.size();
        for (int &i: cnt) i -= n / 4;

        if (check()) return 0;
        
        int  min_size = n;
        for (int l = 0, r = 0; r < n; ++r)
        {
            --cnt[hash[s[r]]];//窗口右端右移

            while (check())//若窗口满足条件
            {
                min_size = min(min_size, r - l + 1);//更新最小窗口长度
                ++cnt[hash[s[l++]]];//窗口左端右移
            }
        }

        return min_size;
    }
};