Leetcode 每日一题 1234. 替换子串得到平衡字符串

简介: 有一个只含有 'Q', 'W', 'E', 'R' 四种字符,且长度为 n 的字符串

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。


🌈个人主页:主页链接


🌈算法专栏:专栏链接


    我会一直往里填充内容哒!


🌈LeetCode专栏:专栏链接


目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出


🌈代码仓库:Gitee链接


🌈点击关注=收获更多优质内容🌈


81019c1cb23444b38595b3e6309b12ba.jpg


本题的核心思想为:滑动窗口(滑动窗口)

忘掉的友友们可以回顾之前的内容进行复习一下 :滑动窗口

题目:


有一个只含有 '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


7c827ac0933e40c6be8a45ded8c9f297.jpg


当区间内为WQWRQ时,窗口外的字母数如图所示,这时将窗口内的字母全部替换成所缺项,即可符合题意


0cd22424c5a0449dbfc8185f64f75f8d.jpg


如图,蓝线是变化的字母,绿线是没有变化的字母(先按下不表) ,这时我们就可以发现,这个子字符串是满足题意的.这个长度为5


我们可以把这个作为答案嘛?显然是不可以的,因为这不是最优解.最简单来看,

当区间内容为QWRQ的时候,也就是左移一个单位,将没有变化的字符串移出去,此时要变化的就是QWRQ

这就体现出了滑动窗口的核心思想:先向右遍历到满足条件的区间,左区间再收缩寻找最优解


4ae39cdef8af489eb344b7988d2371e1.gif


代码实现:


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


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


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


🌈诸君,山顶见!

目录
相关文章
|
1月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
34 6
存储 编译器 Linux
18 0
|
1月前
|
存储
leetcode2744. 最大字符串配对数目
leetcode2744. 最大字符串配对数目
17 0
|
1月前
|
机器学习/深度学习 NoSQL Shell
力扣刷题-翻转字符串
力扣刷题-翻转字符串
12 1
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
21 0
|
1月前
|
Go C++
【力扣】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
【2月更文挑战第17天】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
30 8
|
1月前
|
算法 测试技术 索引
力扣面试经典题之数组/字符串(二)
力扣面试经典题之数组/字符串(二)
13 0
|
22天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
20 2
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记
|
1月前
|
搜索推荐
《LeetCode》——LeetCode刷题日记3
《LeetCode》——LeetCode刷题日记3