【1234. 替换子串得到平衡字符串】
来源:力扣(LeetCode)
描述:
有一个只含有 '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"。
示例 4:
输入:s = "QQQQ"
输出:3
解释:我们可以替换后 3 个 'Q',使 s = "QWER"。
提示:
- 1 <= s.length <= 105
- s.length 是 4 的倍数
- s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符
方法:滑动窗口
思路与算法
设 partial = n / 4 ,我们选择 s 的一个子串作为「待替换子串」,只有当 s 剩余的部分中 ‘Q’,‘W’,‘E’,‘R’ 的出现次数都小于等于 partial 时,我们才有可能使 s 变为「平衡字符串」。
如果原始的 s 就是 「平衡字符串」,我们直接返回 0,否则我们按照以下思路求解。
从小到大枚举「待替换子串」的左端点 l,为了使得替换的长度最小,我们要找到最近的右端点 r,使得去除 [l, r) 之后的剩余部分满足上述条件。不难发现,随着 l 的递增,r 也是递增的。
具体的,我们使用滑动窗口来维护区间 [l, r) 之外的剩余部分中 ‘Q’,‘W’,‘E’,‘R’ 的出现次数,当其中一种字符的出现次数大于 partial 时,令 s[r] 的出现次数减 1,并使得 r 向右移动一个单位。该操作一直被执行,直到条件被满足或者 r 到达 s 的末尾。
如果找到了使得条件被满足的 r,我们用 r − l 来更新答案,然后令 s[l] 的出现次数加 1,并使得 l 向右移动一个单位进行下一次枚举。否则,后序的 l 也将不会有合法的 r,此时我们可以直接跳出循环。对于所有合法的 [l, r),取 r − l 的最小值做为答案。
代码:
class Solution {
public:int idx(const char& c) {return c - 'A';}int balancedString(string s) {vector<int> cnt(26);for (auto c : s) {cnt[idx(c)]++;}int partial = s.size() / 4;int res = s.size();auto check = [&]() {if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial \|| cnt[idx('E')] > partial || cnt[idx('R')] > partial) {return false;}return true;};if (check()) {return 0;}for (int l = 0, r = 0; l < s.size(); l++) {while (r < s.size() && !check()) {cnt[idx(s[r])]--;r++;}if (!check()) {break;}res = min(res, r - l);cnt[idx(s[l])]++;}return res;}
};
执行用时:20 ms, 在所有 C++ 提交中击败了67.46%的用户
内存消耗:7.6 MB, 在所有 C++ 提交中击败了83.33%的用户
复杂度分析
时间复杂度:O(n),其中 n 为 s 的长度。
空间复杂度:O(∣Σ∣),其中 ∣Σ∣ 表示字符集大小,在本题中 ∣Σ∣ = 26。
author:LeetCode-Solution
相关文章:
【1234. 替换子串得到平衡字符串】
来源:力扣(LeetCode) 描述: 有一个只含有 Q, W, E, R 四种字符,且长度为 n 的字符串。 假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。 给你一个这样的字符…...
独自开:提供创业机会、享受平台分红、推出新颖赚钱副业
💗wei_shuo的个人主页 💫wei_shuo的学习社区 🌐Hello World ! 前言 独自开:一款聚焦软件定制开发,独立、自主、开放平台 独创分层标准化平台架构,满足系统不断生长的个性化需求多端一键部署前端业务交互与展…...
C++【二叉树进阶(二叉搜索树)】
文章目录前言1、二叉搜索树1-1、 二叉搜索树概念2、二叉搜索树操作2-1、树和节点的基本框架2-2、二叉搜索树的查找2-3、中序遍历2-4、二叉搜索树的插入2-5、二叉搜索树的删除3、二叉搜索树的模拟实现3-1、循环版本3-2、递归版本4、二叉搜索树的应用4-1、K模型4-2、KV模型4-3、K…...
【C++初阶】vector的使用
大家好我是沐曦希💕 文章目录一.vector介绍二、构造函数三、遍历1.[]2.迭代器3.范围for四、容量操作1.扩容机制五、增删查改六、迭代器失效问题一.vector介绍 vector是表示可变大小数组的序列容器。就像数组一样,vector也采用的连续存储空间来存储元素。…...
OPenPCDet windows流程及其问题
首先的首先极其不推荐将OPenPCDet运行在Windows上,过程非常复杂,适配也不是很好,不推荐在windows下载并训练,本人做这个主要是方便再笔记本电脑上对实验结果进行整理,处理一些简单的推理评估等任务。如有必要请继续阅读: 以下是正文: 常规的安装流程不再赘述,请参考官方…...
【自学Python】Python字符大小写判断
大纲 Python字符串是否是小写 Python字符串是否是小写教程 在开发过程中,有时候我们需要判断一个 字符串 是否是小写形式(即,所有的字符都是小写字母,不是英文字符的忽略不做判断),在 Python 中ÿ…...
设计模式之美总结(开源实战篇)
title: 设计模式之美总结(开源实战篇) date: 2023-01-10 17:13:05 tags: 设计模式 categories:设计模式 cover: https://cover.png feature: false 文章目录1. Java JDK 应用到的设计模式1.1 工厂模式在 Calendar 类中的应用1.2 建造者模式在 Calendar …...
两个月,测试转岗产品经理,我是怎么规划的?
本期同学依旧来自深圳 测试到产品转变,用了两个月 本周,为大家介绍M同学的佛系转岗经历 学员档 学员档案 原岗位:测试 转岗级别:中级产品经理 转岗特点: 1.未接触产品工作 2.对岗位地点要求严格 先看结果 …...
三数之和-力扣15-java排序+双指针
一、题目描述给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意:答案中不可以包含重复的三元组。…...
【编程基础之Python】3、创建Python虚拟环境
【编程基础之Python】3、创建Python虚拟环境创建Python虚拟环境为什么需要虚拟环境Windows上的Anaconda创建虚拟环境conda 命令conda env 命令创建虚拟环境切换虚拟环境验证虚拟环境Linux上的Anaconda创建虚拟环境创建虚拟环境切换虚拟环境验证虚拟环境总结创建Python虚拟环境 …...
kettle开发-Day36-循环驱动作业
前言:在日常数据处理时,我们通过变量传参来完成某个日期的数据转换。但可能因程序或者网络原因导致某个时间段的数据抽取失败。常见导致kettle作业失败的原因大概分为三大类,数据源异常、数据库异常、程序异常。因此面对这些异常时࿰…...
2023秋招 新凯来 算法工程师 面经分享
本专栏分享 计算机小伙伴秋招春招找工作的面试经验和面试的详情知识点 专栏首页:秋招算法类面经分享 主要分享计算机算法类在面试互联网公司时候一些真实的经验 一面 技术面 30分钟左右 1.主要是问项目和论文上的东西,问的不深,中间还介绍他们是做缺陷检测的,大概问了16分钟…...
Web3CN|Damus刷频背后,大众在期待什么样的去中心化社交?
刚过去的一周,许多人的朋友圈包括Twitter、Faceboo在内都在被一串公钥字母刷屏,其重要起因就是 Twitter 前首席执行官 Jack Dorsey 发推称,(2月1日)基于去中心化社交协议 Nostr 的社交产品 Damus 和 Amethyst 已分别在…...
Jenkins自动发布到WindowsServer,在WindowsServer执行的命令
echo off set apppoolname"6.usegitee" set websitename"6.usegitee" set webfolder"usegitee" echo 停止站点的应用程序池 C:\Windows\System32\inetsrv\appcmd.exe stop apppool %apppoolname% echo 停止站点 c:\Windows\System32\inetsrv\a…...
【Git学习】Git如何Clone带有Submodule的仓库?
文章目录一、问题描述二、解决问题三、参考链接四、解决问题4.1 下载主模块4.2 查看主模块的配置4.2 子模块的添加4.3 查看子模块的配置4.4 查看子模块的检出状态4.5 检出submodule4.6 再次查看.git/config4.7 重新打开Android Studio运行代码一、问题描述 在GitHub上下载了一…...
C语言进阶——通讯录模拟实现
🌇个人主页:_麦麦_ 📚今日名言:只有走在路上,才能摆脱局限,摆脱执着,让所有的选择,探寻,猜测,想象都生机勃勃。——余秋雨《文化苦旅》 目录 一、前言 二、正…...
【C#基础】C# 变量和常量的使用
序号系列文章1【C#基础】C# 程序通用结构总结2【C#基础】C# 程序基础语法解析3【C#基础】C# 数据类型总结文章目录前言一. 变量(variable)1,变量定义及初始化2,变量的类别3,接收输出变量二. 常量(constant&…...
nvm安装后出现‘node‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件
出现这个问题多半是path地址不对。 打开系统环境变量。看看path里面有没有?没有的话,加上就行! 我的报错原因就是因为path里没有自动加上nvm的相关路径。 注意项: 1,在安装nvm之前,提前要把本机以前安装…...
张驰咨询:关于六西格玛,有一些常见的疑惑!
很多想要学习六西格玛的学员,经常会有这些困惑: 以前没有接触过六西格玛,需要什么基础吗?自学还是培训?哪些行业会用到六西格玛呢?学习六西格玛对以后的工作有哪些帮助?如何选择六西格玛培…...
【Vercel】教你部署imsyy/home个人主页
本篇博客教你如何部署一个自己的个人主页 项目地址:https://github.com/imsyy/home 本文首发于 慕雪的寒舍 1.fork仓库vercel部署 首先我们点击fork,将仓库复刻到自己的账户 随后进入vercel,点击dashboard-add new-project 选择你复刻的仓库…...
GeekChallenge
2.GeekChallenge 1.web 1.朋友的学妹 url:http://49.234.224.119:7413/ 右键点击查看源码,找到flagU1lDe0YxQF80c19oNExwZnVsbGxsbGx9 然后base64解码得到SYC{F1_4s_h4Lpfullllll} 2.EZwww url:http://47.100.46.169:3901/ 根据网站提示…...
Java文件IO
文章目录Java中的文件操作File常用构造方法方法文件内容的读写——数据流InputStreamFileInputStream利用Scanner进行字符读取OutputStreamPrintWriter按字符读取文件(FileReader)练习代码实例如何按字节进行数据读如何按字节进行数据写如何按字符进行数据读如何按字符进行数据…...
useSSL使用安全套接字协议(史上最全最详细)
useSSL使用安全套接字协议(史上最全最详细) SSL即为:Secure Sockets Layer 安全套接字协议。 useSSLfalse和useSSLtrue的区别: 在MySQL进行连接时: 如果MySQL的版本是5.7之后的版本必须要加上useSSLfalse,…...
面向对象复习(2)
面向对象(2) 对象与引用 java语言中除基本类型之外的变量都称之为引用类型 java中的对象时通过引用对其操作的 Car bm new Car(); 右边的new Car是以Car类为模板,调用无参构造函数,在堆空间中创建一个Car对象 左边的Car bm 在栈中创建了一个Car类型的引用变量,所谓Car的…...
python中使用numpy包的向量矩阵相乘
一直对np的线性运算不太清晰,正好上课讲到了,做一个笔记整个理解一下 1.向量和矩阵 在numpy中,一重方括号表示的是向量vector,vector没有行列的概念。二重方括号表示矩阵matrix,有行列。 代码显示如下: …...
ElasticSearch 学习(一)
目录一、Elasticsearch 简介二、Elasticsearch 发展史三、Elasticsearch 功能四、Elasticsearch 特点五、Elasticsearch 应用场景一、Elasticsearch 简介 Elasticsearch 是一个实时的分布式搜索分析引擎,它能让你以前所未有的速度和规模,去探索你的数据…...
【新】华为OD机试 - 交换字符(Python)| 刷完获取OD招聘渠道
交换字符 题目 给定一个字符串 S 变化规则: 交换字符串中任意两个不同位置的字符 M S 都是小写字符组成 1 <= S.length <= 1000 输入 一串小写字母组成的字符串 输出 按照要求变换得到最小字符串 示例一 输入 abcdef输出 abcdef示例二 输入 bcdefa输出 acde…...
手把手教你解决传说中的NPE空指针异常
1. 前言最近有好几个初学java的小伙伴,甚至是学习到了JavaWeb、框架阶段的小伙伴也跑来问壹哥,该如何解决Java中的NullPointerException空指针异常。因为NPE是初学者特别常见的典型异常,所以壹哥在这里专门写一篇文章,来手把手地教…...
【pytorch安装】conda安装pytorch无法安装cpu版本(完整解决过程)
问题描述 在安装pytorch过程中,发现最后验证torch时总是返回结果为False,结果翻上去发现自己安装的是cpu版本的。 然后又通过conda去更换不同版本尝试,发现都是cpu版本的。 问题分析 通过conda安装pytorch是从源中搜索匹配指令中的文件&am…...
云计算ACP云服务器ECS实例题库
😘作者简介:一名99年软件运维应届毕业生,正在自学云计算课程。👊宣言:人生就是B(birth)和D(death)之间的C(choise),做好每一个选择。&…...
用ps做简单的网页设计/企业网站关键词优化
从自己别的博客搬过来的,很久之前的文章,正好放在专栏Python基础知识里~不知道对别人有没有用,希望不会辣眼睛哈哈~最近学了点关于python的网络爬虫的知识,简单记录一下,这里主要用到了requests库和BeautifulSoup库Req…...
表白时刻网站/济南百度公司
#css基本语法及页面引用 ##css基本语法 css的定义方法是: 选择器 { 属性:值; 属性:值; 属性:值;} 选择器是将样式和页面元素关联起来的名称,属性是希望设置的样式属性每个属性有一个或多个值。代码示例: div{ width:100px; height:100px; …...
商丘做网站优化/分销渠道
https://blog.csdn.net/sidely/article/details/43059795 xrandr --output VGA --auto --output LVDS --off 打开外接显示器,同时关闭笔记本液晶屏幕(只用外接显示器工作) xrandr --output VGA --off --output LVDS --auto 关闭外接显示器…...
网页设计师培训网校/网站seo分析工具
拷贝我们的vector类型具有如下形式:class vector {private:int sz;double * elem; public:vector(int s):sz(s),elem(new double[s]){}~vector() {delete [] elem;} };让我们试图拷贝其中的一个向量:void f(int n) {vector v(3);v.set(2, 2.2);vector v2…...
网站模版好建设吗/seo专业优化方法
zabbix 使用进阶(五)概述:本章内容具体如下:自定义key不带参数;自定义key可传递参数;在agent端自定义可传递参数的key,来获取nginx的状态信息:基于SNMP监控的创建和和使用࿱…...
wordpress真伪查询主题/微博营销策略
当MySQL单表的数据库过大时,数据库的访问速度会下降,“数据量大”问题的常见解决方案是“水平切分”。MySQL常见的水平切分方式有哪些?回答:分库分表,分区表什么是MySQL的分库分表?回答:把一个很…...