目录

题目：1234. 替换子串得到平衡字符串 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：1234. 替换子串得到平衡字符串 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    int balancedString(string s) {

    }
};

解题思路：

这个题目就是让我们求出需要替换子串的最小长度，

我也想不出什么牛逼的解法，

所以就老老实实用哈希和滑动窗口来做，

然后控制一下边界，

具体思路就是：

1. 用一个哈希map存放原字符串以及每个字符的个数，

2. 然后实现一个是否需要替换的的函数，

3. 最后用滑动窗口的思想：

匹配不了 j 就加加，

j 遇到对应字符，该字符就减减，

匹配成功记录下来，然后让 i 加加，看看还有没有更少的替换次数。

i 遇到对应字符，该字符就加加，

直到 j 到边界，且比配失败，将记录的最少的替换次数返回即可。

代码：

class Solution {
public:
    //判断字符串是否平衡
    bool is_balance(int m, unordered_map<char, int>& mp)
    {
        for(const auto& it : mp)
        {
            //如果字符个数大于n/4，当然不平衡
            if(it.second > m)
            {
                return false;
            }
        }
        //字符个数都等于n/4，平衡了
        return true;
    }

    int balancedString(string s) {
        int n = s.size();
        int m = n / 4;

        //建一个哈希map
        unordered_map<char, int> mp;

        //把字符都存进去
        for(char e : s)
        {
            mp[e]++;
        }

        //用这个判断函数判断是否已经匹配成功
        if(is_balance(m, mp))
        {
            return 0;
        }

        //这里创建ret为一个很大的数，用来作为初始的比较数
        int i = 0, j = 0, ret = INT_MAX, breakcnt = 0;

        //滑动窗口[i, j) 
        while(i < n)
        {
            //如果平衡，动i，看看还有没有更优解
            if(is_balance(m, mp))
            {
                int tmp = j - i;

                //记录最小替换次数
                ret = min(ret, tmp);

                //下标i离开了s[i]，让该字符数量++（因为不替换这个字符了）
                mp[s[i]]++;
                i++;
            }
            else
            {
                if(j < n)//j到边界就停下来
                {
                    //下标j往后移动，让该字符数量--（在滑动窗口内的字符是要被替换的）
                    mp[s[j]]--;
                    j++;
                }
                else//j到边界了
                {
                    breakcnt++;
                    //先别直接break，让窗口再匹配一次，看看还有没有更优解
                    //如果没有，第二次到这里就break。
                    if(breakcnt > 1)
                    {
                        break;
                    }
                }
            }
        }
        //返回记录的最小替换次数
        return ret;
    }
};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。