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

算法刷题打卡第97天:删除字符串两端相同字符后的最短长度

删除字符串两端相同字符后的最短长度

难度:中等

给你一个只包含字符 'a''b''c' 的字符串 s ,你可以执行下面这个操作(5 个步骤)任意次:

  • 选择字符串 s 一个 非空 的前缀,这个前缀的所有字符都相同。
  • 选择字符串 s 一个 非空 的后缀,这个后缀的所有字符都相同。
  • 前缀和后缀在字符串中任意位置都不能有交集。
  • 前缀和后缀包含的所有字符都要相同。
  • 同时删除前缀和后缀。

请你返回对字符串 s 执行上面操作任意次以后(可能 0 次),能得到的 最短长度

双指针

思路:

题目要求删除字符串 sss 中字母相同且不相交的前缀与后缀,假设当前字符串的长度为 nnn,则执行的删除规则如下:

  • 选择字符串 sss 一个非空的前缀 prefix=s[0,⋯,l]\textit{prefix} = s[0,\cdots,l]prefix=s[0,,l],这个前缀的所有字符都相同,s[0]=s[1]=⋯=s[l]s[0] = s[1] = \cdots = s[l]s[0]=s[1]==s[l]
  • 选择字符串 sss 一个非空11的后缀 suffix=s[r,⋯,n−1]\textit{suffix} = s[r,\cdots,n-1]suffix=s[r,,n1],这个后缀的所有字符都相同,s[r]=s[r+1]=⋯=s[n−1]s[r] = s[r + 1] = \cdots = s[n-1]s[r]=s[r+1]==s[n1]
  • 前缀和后缀在字符串中任意位置都不能有交集,即 l<rl < rl<r
  • 前缀和后缀包含的所有字符都要相同,s[0]=s[1]=⋯=s[l]=s[r]=s[r+1]=⋯=s[n−1]s[0] = s[1] = \cdots = s[l] = s[r] = s[r + 1] = \cdots = s[n-1]s[0]=s[1]==s[l]=s[r]=s[r+1]==s[n1]
  • 同时删除前缀和后缀。

通过观察我们对 sss 进行分类讨论如下:

  • sss 的长度为 111 时,假设 s=“a"s = \text{``a"}s=“a",此时按照题目的删除规则此时不能删除。
  • sss 的长度大于 111sss 中的所有字符均相同,假设 s=“aaaa"s = \text{``aaaa"}s=“aaaa",此时按照题目的删除规则 sss 一定可以全部删除完。
  • sss 的长度大于 111sss 存在字母相同的前缀与后缀,假设 s=“aaabbbccca"s = \text{``aaabbbccca"}s=“aaabbbccca",此时按照题目的删除规则最优选择是 sss 应当将前缀与后缀中连续的 ‘a’\text{`a’}‘a’ 全部删除完,删除完成后 s′=“bbbccc"s' = \text{``bbbccc"}s=“bbbccc"
  • sss 的长度大于 111sss 不存在字母相同的前缀与后缀,假设 s=“aaaccc"s = \text{``aaaccc"}s=“aaaccc",此时按照删除规则,无法进行删除。

根据以上的删除规则分类,我们设 left\textit{left}leftright\textit{right}right 分别指向当前待删除字符串的起始位置与结束位置,然后按照规则进行删除,当前可以删除的条件必须满足如下:

  • 只有字符串的长度大于 111 时我们才进行删除,因此可以进行删除的条件一定需要满足 left<right\textit{left} < \textit{right}left<right
  • 只有存在字母相同的前缀与后缀我们才进行删除,因此可以进行删除的条件一定需要满足 s[left]=s[right]s[\textit{left}] = s[\textit{right}]s[left]=s[right]

假设有可以进行删除的前缀和后缀时,则我们将所有字母相同的前缀与后缀全部删除,此时 left\textit{left}left 需要向右移动,right\textit{right}right 需要向左移动,并删除字符串中字母相同的前缀与后缀,直到无法删除为止。最终 left\textit{left}left 指向删除后字符串的左起点,right\textit{right}right 指向删除后字符串的右终点,剩余的字符串的长度则为 right−left+1\textit{right} - \textit{left} + 1rightleft+1

需要注意的是,如果当 sss 的长度大于 111sss 中的字符全部相等时,此时需要将 sss 全部进行删除,则会出现 right=left−1\textit{right} = \textit{left} - 1right=left1

复杂度分析:

  • 时间复杂度: O(n)O(n)O(n),其中 nnn 表示字符串的长度。我们只需遍历一遍字符串即可。
  • 空间复杂度: O(1)O(1)O(1)
class Solution:def minimumLength(self, s: str) -> int:l, r = 0, len(s) - 1while r - l >= 1 and s[l] == s[r]:now = s[l]while l <= r and s[l] == now:l += 1while l <= r and s[r] == now:r -= 1return r - l + 1

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-length-of-string-after-deleting-similar-ends/

相关文章:

算法刷题打卡第97天:删除字符串两端相同字符后的最短长度

删除字符串两端相同字符后的最短长度 难度&#xff1a;中等 给你一个只包含字符 a&#xff0c;b 和 c 的字符串 s &#xff0c;你可以执行下面这个操作&#xff08;5 个步骤&#xff09;任意次&#xff1a; 选择字符串 s 一个 非空 的前缀&#xff0c;这个前缀的所有字符都相…...

WebGPU学习(3)---使用IndexBuffer(索引缓冲区)

现在让我们将 IndexBuffer 与 VertexBuffer 一起使用。演示示例 1.准备索引数据 我们用 Uint16Array 类型来准备索引数据。我们将矩形的4个点放到 VertexBuffer 中&#xff0c;然后根据三角形绘制顺序&#xff0c;组织成 0–1–2 和 0–2–3 的结构。 const quadIndexArray …...

Java代码加密混淆工具有哪些?

在Java中&#xff0c;代码加密混淆工具可以帮助开发者将源代码进行加密和混淆处理&#xff0c;以增加代码的安全性和保护知识产权。以下是一些流行的Java代码加密混淆工具&#xff1a; 第一款&#xff1a;ProGuard&#xff1a;ProGuard      ProGuard&#xff1a;ProGuard…...

华为OD机试 - 高效的任务规划(Python) | 机试题+算法思路+考点+代码解析 【2023】

高效的任务规划 题目 你有 n 台机器编号为1-n,每台都需要完成一项工作, 机器经过配置后都能独立完成一项工作。 假设第i台机器你需要花 Bi 分钟进行设置, 然后开始运行,Ji分钟后完成任务。 现在,你需要选择布置工作的顺序,使得用最短的时间完成所有工作。 注意,不能同…...

ChatGPT写程序如何?

前言ChatGPT最近挺火的&#xff0c;据说还能写程序&#xff0c;感到有些惊讶。于是在使用ChatGPT有一周左右后&#xff0c;分享一下用它写程序的效果如何。1、对于矩阵&#xff0c;把减法操作转换加法&#xff1f;感觉不错的&#xff0c;能清晰介绍原理&#xff0c;然后写示例程…...

编译链接实战(9)elf符号表

文章目录符号的概念符号表探索前面介绍了elf文件的两种视图&#xff0c;以及两种视图的各自几个组成部分&#xff1a;elf文件有两种视图&#xff0c;链接视图和执行视图。在链接视图里&#xff0c;elf文件被划分成了elf 头、节头表、若干的节&#xff08;section&#xff09;&a…...

React合成事件的原理是什么

事件介绍 什么是事件&#xff1f; 事件是在编程时系统内发生的动作或者发生的事情&#xff0c;而开发者可以某种方式对事件做出回应&#xff0c;而这里有几个先决条件 事件对象 给事件对象注册事件&#xff0c;当事件被触发后需要做什么 事件触发 举个例子 在机场等待检票…...

Arduino-交通灯

LED交通灯实验实验器件&#xff1a;■ 红色LED灯&#xff1a;1 个■ 黄色LED灯&#xff1a;1 个■ 绿色LED灯&#xff1a;1 个■ 220欧电阻&#xff1a;3 个■ 面包板&#xff1a;1 个■ 多彩杜邦线&#xff1a;若干实验连线1.将3个发光二极管插入面包板&#xff0c;2.用杜邦线…...

【论文笔记】Manhattan-SDF == ZJU == CVPR‘2022 Oral

Neural 3D Scene Reconstruction with the Manhattan-world Assumption 本文工作&#xff1a;基于曼哈顿世界假设&#xff0c;重建室内场景三维模型。 1.1 曼哈顿世界假设 参考阅读文献&#xff1a;Structure-SLAM: Low-Drift Monocular SLAM in Indoor EnvironmentsIEEE IR…...

好消息!Ellab(易来博)官方微信公众号开通了!携虹科提供专业验证和监测解决方案

自1949年以来&#xff0c;丹麦Ellab一直通过全球范围内的验证和监测解决方案&#xff0c;协助全球生命科学和食品公司优化和改进其流程的质量。Ellab全面的无线数据记录仪&#xff0c;热电偶系统&#xff0c;无线环境监测系统&#xff0c;校准设备&#xff0c;软件解决方案等等…...

想要去字节跳动面试Android岗,给你这些面试知识点

关于面试字节跳动&#xff0c;我总结一些面试点&#xff0c;希望可以帮到更多的小伙伴&#xff0c;由于篇幅问题这里没有把全部的面试知识点问题都放上来&#xff01;&#xff01;目录&#xff1a;1.网络2.Java 基础&容器&同步&设计模式3.Java 虚拟机&内存结构…...

Java的Lambda表达式的使用

Lambda表达式是Java 8中引入的一个重要特性&#xff0c;它是一种简洁而强大的语法结构&#xff0c;可以用于替代传统的匿名内部类。 Lambda表达式的语法结构如下&#xff1a; (parameters) -> expression或者 (parameters) -> { statements; }其中&#xff0c;paramet…...

Spring MVC 源码 - HandlerMapping 组件(三)之 AbstractHandlerMethodMapping

HandlerMapping 组件HandlerMapping 组件&#xff0c;请求的处理器匹配器&#xff0c;负责为请求找到合适的 HandlerExecutionChain 处理器执行链&#xff0c;包含处理器&#xff08;handler&#xff09;和拦截器们&#xff08;interceptors&#xff09;handler 处理器是 Objec…...

超店有数,为什么商家要使用tiktok达人进行营销推广呢?

近几年互联网发展萌生出更多的短视频平台&#xff0c;而tittok这个平台在海外也越来越火爆。与此同时&#xff0c;很多商家也开始用tiktok进行营销推广。商家使用较多的方式就是达人营销&#xff0c;这种方法很常见且转化效果不错。那为什么现在这么多商家喜欢用tiktok达人进行…...

【分享】订阅万里牛集简云连接器同步企业采购审批至万里牛系统

方案场景 面临着数字化转型的到来&#xff0c;不少公司希望实现业务自动化需求&#xff0c;公司内部将钉钉作为办公系统&#xff0c;万里牛作为ERP系统&#xff0c;两个系统之前的数据都储存在各自的后台&#xff0c;导致数据割裂&#xff0c;数据互不相通&#xff0c;人工手动…...

C++类和对象_02----对象模型和this指针

目录C对象模型和this指针1、成员变量和成员函数分开存储1.1、空类大小1.2、非空类大小1.3、结论2、this指针概念2.1、解决名称冲突2.2、在类的非静态成员函数中返回对象本身&#xff0c;可使用return *this2.3、拷贝构造函数返回值为引用的时候&#xff0c;可进行链式编程3、空…...

瑞芯微RK3568开发:烧录过程

进入rk3568这款芯片的烧录模式共有3种方式&#xff0c;先讲需要准备的环境要求。 一、软硬件环境 1、配套sdk版本的驱动DriverAssitant_vx.x.x和RKDevTool_Release_vx.x&#xff0c;版本不对应可能无法烧录&#xff0c;建议直接在sdk压缩包里获取&#xff1b; 2、如果正确安…...

【数据结构】——树和二叉树的概念

目录 1.树概念及结构 1.1树的概念 1.2 树的相关性质 1.3 树的表示 1.4 树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09; 2.二叉树概念及结构 2.1二叉树概念 2.2 特殊的二叉树 2.3 二叉树的性质 1.树概念及结构 1.1树的概念 树是一种非线性的数据结构…...

Meta分析在生态环境领域里的应用

Meta分析&#xff08;Meta Analysis&#xff09;是当今比较流行的综合具有同一主题的多个独立研究的统计学方法&#xff0c;是较高一级逻辑形式上的定量文献综述。20世纪90年代后&#xff0c;Meta分析被引入生态环境领域的研究&#xff0c;并得到高度的重视和长足的发展&#x…...

PrivateLoader PPI服务发现RisePro恶意软件窃取分发信息

称为PrivateLoader的按安装付费&#xff08;PPI&#xff09;软件下载器服务正用于恶意软件RisePro的信息窃取。Flashpoint 于 2022 年 12月13日发现了新的窃取者&#xff0c;此前发现了在名为Russian Market的非法网络犯罪市场上使用该恶意软件泄露的“几组日志”。RisePro是一…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...