当前位置: 首页 > news >正文

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

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

题目描述

有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符,且长度为 n 的字符串。

假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。

给你一个这样的字符串 s,请通过「替换一个子串」的方式,使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串,则返回 0。


示例 1

输入:s = “QWER”
输出:0
解释:s 已经是平衡的了。


示例 2

输入:s = “QQWE”
输出:1
解释:我们需要把一个 ‘Q’ 替换成 ‘R’,这样得到的 “RQWE” (或 “QRWE”) 是平衡的。

示例 3

输入:s = “QQQW”
输出:2
解释:我们可以把前面的 “QQ” 替换成 “ER”。


提示

  • 1 <= s.length <= 105
  • s.length 是 4 的倍数
  • s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符

算法一:计数+双指针(滑动窗口)

思路

  • 首先使用一个哈希表统计四个字符的出现次数, 「当四个字符的出现次数不超过 s.size() / 4 」时, 不需要替换子串,直接返回 0。
  • 否则, 使用双指针 i , j 维护滑动窗口的左右边界, 初始都设置为 0 。
  • 接下来,遍历字符串 s, 每次遍历到某字符, 就将它的出现次数减一, 然后判断当前窗口是否满足条件,即窗口外的字符数量都不超过 s.size() / 4 ,如果满足条件,那么就更新答案, 然后就将窗口左移(右边界 i 固定, 增大 j ,所以窗口变小), 直到不满足条件为止。

收获

  • 我没有注意到题目要求的是将子串替换,也就是需要将连续个字符替换,因此一开始方向错了;
  • 题解用了 t.find(s[i]) ,更方便计数,这个需要学习;
  • 此外,还学习了 移动窗口 的思想。

算法情况

  • 时间复杂度:O(n),其中 n 为字符串 s 的长度;
  • 空间复杂度:O(C),C 为 4。

代码

class Solution {
public:int balancedString(string s) {int n = s.size();int m = n / 4; // 每个字符出现次数string t = "QWER";vector<int> cnt(4);for(auto &c : s){cnt[t.find(c)]++;}if(cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m){return 0;}int ans = n;for(int i = 0, j = 0; i < n; ++i){cnt[t.find(s[i])]--;while(j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m){ans = min(ans, i - j + 1);// i不变,j指针右移,缩小窗口cnt[t.find(s[j++])]++;}}return ans;}
};

参考资料:

  1. string.find()的用法
http://www.lryc.cn/news/4557.html

相关文章:

  • [动手写操作系统]-01-开机运行系统
  • 最长回文子序列问题
  • 月薪11k!从财务专员到软件测试工程师,成都校区小哥哥用三个月实现转行换岗
  • Android 逆向工具大整理,碉堡了
  • 二维数组的定义
  • SpringMVC--获取请求参数、域对象共享数据
  • 2月13日,30秒知全网,精选7个热点
  • 【C++设计模式】学习笔记(2):模式分类与模版方法 Template Method
  • 【Swift 60秒】92 - Nil coalescing
  • python pip安装的包的路径
  • 个人收藏学习
  • 【C++】类和对象---需掌握的功能
  • 2.12、进程互斥的软件实现方法
  • Java面试题-数据库
  • select 与 where、group by、order by、limit 子句执行优先级比较
  • 【Docker】用开源umami监控你的站点访问量
  • java环境配置
  • Linux系统服务:Apache安装及配置应用
  • 动态规划(Dynamic Programming)——背包问题
  • JVM学习02:内存结构
  • 6年软件测试经验,从我自己的角度理解自动化测试
  • 三种方式查看linux终端terminal是否可以访问外网ping,curl,wget
  • 【Call for papers】SIGCOMM-2023(CCF-A/计算机网络/2023年2月15日截稿)
  • Chapter5:机器人感知
  • [acwing周赛复盘] 第 90 场周赛20230211 补
  • 数组
  • MicroBlaze系列教程(4):AXI_UARTLITE的使用
  • GO 中的 init 函数
  • 使用C#编写k8s CRD Controller
  • Ansible---playbook剧本