Leetcode 每日一题 1234. 替换子串得到平衡字符串
Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
目录
题目：
白话讲解：
题例:
题解:
代码实现:
完结撒花：
本题的核心思想为：滑动窗口（滑动窗口）
忘掉的友友们可以回顾之前的内容进行复习一下 ：滑动窗口
题目：
有一个只含有
'Q', 'W', 'E', 'R'四种字符，且长度为n的字符串。假如在该字符串中，这四个字符都恰好出现
n/4次，那么它就是一个「平衡字符串」。给你一个这样的字符串
s，请通过「替换一个子串」的方式，使原字符串s变成一个「平衡字符串」。你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回
0。
白话讲解：
有一个长度为4的倍数的字符串，其中出现四类字符QWER若这四类字符出现的次数为n/4则认为这是一个平衡字符串,返回0
若不为平衡字符串,则需要替换其中连续的子字符串,返回替换最短子字符串的长度.
题例:
输入：s = "QWER" 输出：0 解释：s 已经是平衡的了。输入：s = "QQWE" 输出：1 解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。输入：s = "QQQW" 输出：2 解释：我们可以把前面的 "QQ" 替换成 "ER"。输入：s = "QQQQ" 输出：3 解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
题解:
观察题意可知,以滑动窗口为分界点,若 窗口外的字母每类字母<=n/4 则将窗口内的字母全部替换就满足题意了.
举个例子:WQWRQQW
当区间内为WQWRQ时,窗口外的字母数如图所示,这时将窗口内的字母全部替换成所缺项,即可符合题意
如图,蓝线是变化的字母,绿线是没有变化的字母(先按下不表) ,这时我们就可以发现,这个子字符串是满足题意的.这个长度为5
我们可以把这个作为答案嘛?显然是不可以的,因为这不是最优解.最简单来看,
当区间内容为QWRQ的时候,也就是左移一个单位,将没有变化的字符串移出去,此时要变化的就是QWRQ
这就体现出了滑动窗口的核心思想:先向右遍历到满足条件的区间,左区间再收缩寻找最优解
代码实现:
#include <algorithm>
#include<iostream>
#include<string>
using namespace std;
class Solution {
public:int balancedString(string s) {int cnt[26]={0};int n=s.size();for(char c:s)cnt[c-'A']++;int ans=INT_MAX;if(cnt['Q'-'A']==n/4&&cnt['W'-'A']==n/4&&cnt['E'-'A']==n/4&&cnt['R'-'A']==n/4)return 0;//已经排完序for(int i=0,j=0;j<n;j++)//遍历右端点{cnt[s[j]-'A']--;//更新刚刚新加入窗口的元素while(i<=j&&cnt['Q'-'A']<=n/4&&cnt['W'-'A']<=n/4&&cnt['E'-'A']<=n/4&&cnt['R'-'A']<=n/4)//窗口外的所有元素数量都小于等于要求答案{ans=min(ans,j-i+1);//说明当前区间内的所有元素都变换即可满足题意，更新区间cnt[s[i]-'A']++;//寻找最小的情况i++;}}return ans;}
};完结撒花：
🌈本篇博客的内容【Leetcode 每日一题 1234. 替换子串得到平衡字符串】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！