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

LeetCode 1653. 使字符串平衡的最少删除次数

LeetCode 1653. 使字符串平衡的最少删除次数

难度:middle\color{orange}{middle}middle

Rating:1794\color{orange}{1794}1794


题目描述

给你一个字符串 sss ,它仅包含字符 ′a′'a'a′b′'b'b​​​​ 。

你可以删除 sss 中任意数目的字符,使得 sss 平衡 。当不存在下标对 (i,j)(i,j)(i,j) 满足 i<ji < ji<j ,且 s[i]=′b′s[i] = 'b's[i]=b 的同时 s[j]=′a′s[j]= 'a's[j]=a ,此时认为 sss平衡 的。

请你返回使 sss 平衡最少 删除次数。

示例 1:

输入:s = "aababbab"
输出:2
解释:你可以选择以下任意一种方案:
下标从 0 开始,删除第 2 和第 6 个字符("aababbab" -> "aaabbb"),
下标从 0 开始,删除第 3 和第 6 个字符("aababbab" -> "aabbbb")。

示例 2:

输入:s = "bbaaaaabb"
输出:2
解释:唯一的最优解是删除最前面两个字符。

提示:

  • 1<=s.length<=1051 <= s.length <= 10^{5}1<=s.length<=105
  • s[i]s[i]s[i] 要么是 ′a′'a'a 要么是 ′b′'b'b​ 。​

算法

(枚举)

通过删除部分字符串,使得字符串达到下列三种情况之一,即为平衡状态:

  • 字符串全为 “a”;
  • 字符串全为 “b”;
  • 字符串既有 “a” 也有 “b”,且所有 “a” 都在所有 “b” 左侧。

为了达到第 1 种情况,最少需要删除所有的 “b”。

为了达到第 2 种情况,最少需要删除所有的 “a”。

而第 3 种情况,可以在原字符串相邻的两个字符之间划一条间隔,删除间隔左侧所有的 “b” 和间隔右侧所有的 “a” 即可达到。用 leftb 表示间隔左侧的 “b” 的数目,righta 表示间隔左侧的 “a” 的数目,leftb+righta 即为当前划分的间隔下最少需要删除的字符数。这样的间隔一共有 n−1 种,其中 n 是 s 的长度。遍历字符串 s,即可以遍历 n−1 种间隔,同时更新 leftb 和 righta 的数目。而上文讨论的前两种情况,其实就是间隔位于首字符前和末字符后的两种特殊情况,可以加入第 3 种情况一并计算。

复杂度分析

  • 时间复杂度O(n)O(n)O(n),其中 nnn 是链表的长度。需要遍历链表一次

  • 空间复杂度 : O(1)O(1)O(1)

C++ 代码

class Solution {
public:int minimumDeletions(string s) {int righta = 0;for (int i = 0; i < s.size(); i ++) {if (s[i] == 'a') righta ++;}int res = righta;int leftb = 0;for (int i = 0; i < s.size(); i ++) {if (s[i] == 'a')righta --;else leftb ++;res = min(res, leftb + righta);}return res;}
};

相关文章:

LeetCode 1653. 使字符串平衡的最少删除次数

LeetCode 1653. 使字符串平衡的最少删除次数 难度&#xff1a;middle\color{orange}{middle}middle Rating&#xff1a;1794\color{orange}{1794}1794 题目描述 给你一个字符串 sss &#xff0c;它仅包含字符 ′a′a′a′ 和 ′b′b′b′​​​​ 。 你可以删除 sss 中任意…...

聊一聊代码重构——程序方法和类上的代码实践

使用工厂方法取代构造方法 构造方法的问题 我们使用构造方法来初始化对象时候&#xff0c;我们得到的只能是当前对象。而使用工厂方法替换构造方法&#xff0c;我们可以返回其子类型或者代理类型。这让我们可以通过不同的实现类来进行逻辑实现的变化。 更重要的一点是&#…...

嵌入式学习笔记——寄存器开发STM32 GPIO口

寄存器开发STM32GPIO口前言认识GPIOGPIO是什么GPIO有什么用GPIO怎么用STM32上GPIO的命名以及数量GPIO口的框图&#xff08;重点&#xff09;输入框图解析三种输入模式GPIO输入时内部器件及其作用1.保护二极管2.上下拉电阻&#xff08;可配置&#xff09;3.施密特触发器4.输入数…...

[ 攻防演练演示篇 ] 利用通达OA 文件上传漏洞上传webshell获取主机权限

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…...

程序设计与 C 语言期末复习

程序设计与 C 语言 1.计算机语言与编译 机器语言&#xff1a;一串仅由 0 和 1 序列表示的语言。计算机只能识别和接受 0 和 1 组成的指令。 符号语言&#xff08;汇编语言&#xff09;&#xff1a;用一些英文字母和数字表示一个指令。 符号语言&#xff08;汇编语言&#xf…...

05-思维导图Xmind快速入门

文章目录5.1 认识思维导图5.2 Xmind的主要结构及主题元素5.2.1 Xmind的多种结构5.2.2 主题分类5.2.3 Xmind的主题元素章节总结5.1 认识思维导图 什么是思维导图&#xff1f; 思维导图是一种将思维进行可视化的实用工具。 具体实现方法是用一个关键词去引发相关想法&#xff0…...

使用去中心化存储构建网站

今天的大多数网站都遵循后端服务器到前端代码的架构。但在 Web3 应用程序中&#xff0c;前端代码不具有与受智能合约保护的后端代码相同的去中心化性和弹性。那么如何使网站像智能合约一样具有弹性呢&#xff1f; 该体系结构似乎很简单&#xff1a; 创建一个没有服务器的静态…...

L - Let‘s Swap(哈希 + 规律)

2023河南省赛组队训练赛&#xff08;四&#xff09; - Virtual Judge (vjudge.net) 约瑟夫最近开发了一款名为Pandote的编辑软件&#xff0c;现在他正在测试&#xff0c;以确保它能正常工作&#xff0c;否则&#xff0c;他可能会被解雇!Joseph通过实现对Pandote上字符串的复制和…...

c语言自动内存回收(RAII实现)

简述 什么是RAII RAII&#xff08;Resource Acquisition Is Initialization&#xff09;是c之父Bjarne Stroustrup提出的概念。资源一般分三个步骤&#xff1a;获取、使用和销毁&#xff0c;而在自由使用内存的c语言中&#xff0c;资源的销毁常常是程序员容易遗漏的事情&…...

Node.js的简单学习一-----未完待续

文章目录前言学习目标一、初识Node.js1.1 回顾与思考1.1.1 需要掌握那些技术1.1.2 浏览器中的JavaScript的组成部分1.2 Node.js简介1 什么是Node.js2 Node.js中的JavaScript运行环境3 Node.js 可以做什么1.3 Node.js环境的安装1.4 在Node.js环境中执行JavaScript 代码终端中的快…...

linux入门---粘滞位

为什么会有粘滞位 一台服务器有很多人使用&#xff0c;每个人在机器上都会有一个家目录&#xff0c;在家目录里可以实现自己想要的操作&#xff0c;但是有时候我们需要一个公共路径来完成一些操作&#xff0c;比如说资料分享产生临时文件的增删查改等等&#xff0c;这就好比我…...

关于正则表达式的讲解

以下内容源于《linux命令行与shell脚本编程大全【第三版】》一书的整理。 在shell脚本中成功运用sed编辑器和gawk程序的关键&#xff0c;在于熟练地使用正则表达式。 一、正则表达式的简介 1、正则表达式的定义 正则表达式&#xff08;regular expression&#xff09;是一个…...

贝塞尔曲线与B样条曲线

文章目录0.参考1.问题起源与插值法的曲线拟合1.1.问题起源1.2.拉格朗日插值1.3.“基”的概念1.4.插值存在的Runge现象2.贝塞尔曲线2.1.控制点的思想2.2.由控制点生成贝塞尔曲线2.3.多个控制点时的贝塞尔曲线公式2.4.贝塞尔曲线的递推公式2.5.贝塞尔曲线的性质3.B样条曲线3.1.B样…...

C语言-基础了解-24-C头文件

C头文件 一、C 头文件 头文件是扩展名为 .h 的文件&#xff0c;包含了 C 函数声明和宏定义&#xff0c;被多个源文件中引用共享。有两种类型的头文件&#xff1a;程序员编写的头文件和编译器自带的头文件。 在程序中要使用头文件&#xff0c;需要使用 C 预处理指令 #include…...

The 19th Zhejiang Provincial Collegiate Programming Contest vp

和队友冲了这场&#xff0c;极限6题&#xff0c;重罚时铁首怎么说&#xff0c;前面的A题我贡献了太多的罚时&#xff0c;然后我的G题最短路调了一万年&#xff0c;因为太久没写了&#xff0c;甚至把队列打成了优先队列&#xff0c;没把head数组清空完全&#xff0c;都是我的锅呜…...

用于<分类>的卷积神经网络、样本不平衡问题的解决

输入图像——卷积层——池化层——全连接层——输出 卷积层&#xff1a;核心&#xff0c;用来提取特征。 池化层&#xff1a;对特征降维。实际的主要作用是下采样&#xff0c;减少参数量来提高计算速度。 卷积神经网络的训练&#xff1a;前向传播&#xff08;分类识别&#xf…...

网上订餐管理系统的设计与实现

技术&#xff1a;Java、JSP等摘要&#xff1a;随着信息技术的广泛使用&#xff0c;电子商务对于提高管理和服务水平发挥着关键的作用。越来越多的商家开始着手于电子商务建设。电子商务的发展为人们的生活提供了极大的便利&#xff0c;也成为现实社会到网络社会的真实体现。当今…...

Httpclient测试

在IDEA中有一个非常方便的http接口测试工具httpclient&#xff0c;下边介绍它的使用方法&#xff0c;后边我们会用它进行接口测试。如果IDEA版本较低没有自带httpclient&#xff0c;需要安装httpclient插件1.插件2.controller进入controller类&#xff0c;找到http接口对应的方…...

EXCEL里的各种奇怪计算问题:数字后面自动多了 0.0001, 数字后面位数变成000,以及一些取整,数学函数

1 公式计算后的数&#xff0c;用只粘贴数值后&#xff0c;后面自动多了 0.0001&#xff0c;导致不再是整数的问题 问题入戏 见第1个8400&#xff0c;计算时就出现了问题&#xff0c;按正常&#xff0c;这里8400应该是整数&#xff0c;而不应该带小数&#xff0c;但是确实就计…...

PHP CRUL请求GET、POST

// GET请求 public function curlGet($url,$header){ $ch curl_init(); curl_setopt($ch, CURLOPT_HTTPHEADER, $header); curl_setopt($ch, CURLOPT_URL, $url); curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, FALSE); curl_setopt($ch, CURLOPT_SSL_VERIFYHOST, FALSE); curl_s…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001

qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类&#xff0c;直接把源文件拖进VS的项目里&#xff0c;然后VS卡住十秒&#xff0c;然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分&#xff0c;导致编译的时候找不到了。因…...