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. 替换子串得到平衡字符串】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！