LeetCode 1156.单字符重复子串的最大长度

如果字符串中的所有字符都相同,那么这个字符串是单字符重复的字符串。

给你一个字符串 text,你只能交换其中两个字符一次或者什么都不做,然后得到一些单字符重复的子串。返回其中最长的子串的长度。

示例 1:

输入:text = “ababa”
输出:3
示例 2:

输入:text = “aaabaaa”
输出:6
示例 3:

输入:text = “aaabbaaa”
输出:4
示例 4:

输入:text = “aaaaa”
输出:5
示例 5:

输入:text = “abcdef”
输出:1

提示:

1 <= text.length <= 20000
text 仅由小写英文字母组成。

滑动窗口,保证窗口内最多有两种字符,有两种字符时,保证一种字符的数量为1。
当窗口内有两种字符时,如果窗口大小为winSize,其中一种字符a的数量为1,另一种字符b的数量就是n-1
如果数量为n-1的字符a在窗口外还有字符,则整个窗口都是合法的子串,因为可以把窗口外的一个字符a和窗口内的字符b交换位置;否则窗口内合法的子串长度就是n-1,因为可以自由交换窗口内的字符b到窗口两端点。
找出最大的窗口内合法子串长度即可。

class Solution {
public:int maxRepOpt1(string text) {int cnt[26];for (char c : text) {++cnt[c - 'a'];}int left = 0;int ans = 0;map<char, int> cur;for (int i = 0; i < text.size(); ++i) {++cur[text[i]];while (cur.size() == 3 || cur.size() == 2 &&cur.rbegin()->second >= 2 && cur.begin()->second >= 2) {if (--cur[text[left]] == 0) {cur.erase(text[left]);}++left;}char more = cur.rbegin()->first;if (cur.begin()->second > cur.rbegin()->second) {more = cur.begin()->first;}int len = min(cnt[more - 'a'], i - left + 1);ans = max(ans, len);}return ans;}
};

如果text的长度为n,其中的字符种类数为m,则此算法时间复杂度为O(n),空间复杂度为O(m),本题m为26。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.tpcf.cn/web/89267.html

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

K近邻算法的分类与回归应用场景

K近邻算法的分类与回归应用场景 K近邻&#xff08;K-Nearest Neighbors, KNN&#xff09;算法是一种基础但强大的机器学习方法&#xff0c;它既可以用于分类问题&#xff0c;也能解决回归问题。 两者的核心思想都是基于"近朱者赤&#xff0c;近墨者黑"的原理&#xf…

算法精讲--正则表达式(二):分组、引用与高级匹配技术

算法精讲–正则表达式&#xff08;二&#xff09;&#xff1a;分组、引用与高级匹配技术 &#x1f680;正则表达式的真正力量在于组合使用各种语法元素&#xff0c;创造出强大而精确的匹配模式&#xff01; —— 作者&#xff1a;无限大 推荐阅读时间&#xff1a;25 分钟 适用人…

python+requests 接口自动化测试实战

首先介绍一下python的requests模块&#xff1a; requests的使用介绍&#xff1a;requests快速入门 Python结合requests库实现接口自动化测试环境说明&#xff1a; 1.WIN 7, 64位 2.Python3.4.3 &#xff08;pip-8.1.2&#xff09; 3.Requests —>pip install requests 4.U…

NAT 实验

NAT 实验 一.实验拓扑图实验目的 1.按照图示配置 IP 地址 2.私网 A 通过 R1 接入到互联网&#xff0c;私网 B 通过 R3 接入到互联网 3.私网 A 内部存在 Vlan10 和 Vlan20&#xff0c;通过 R1 上单臂路由访问外部网络 4.私网 A 通过 NAPT 使 Vlan10 和 Vlan20 都能够使用 R1 的公…

buuctf——web刷题第三页

第三页 目录 [FBCTF2019]RCEService [0CTF 2016]piapiapia [Zer0pts2020]Can you guess it? [WUSTCTF2020]颜值成绩查询 [SUCTF 2019]Pythonginx [MRCTF2020]套娃 [CSCCTF 2019 Qual]FlaskLight [watevrCTF-2019]Cookie Store [WUSTCTF2020]CV Maker [红明谷CTF 202…

前后端分离项目中的接口设计与调用流程——以高仙机器人集成为例

一、背景介绍在前后端分离项目开发中&#xff0c;前端页面需要频繁调用后端接口获取数据。在高仙机器人对接项目中&#xff0c;我们采用了若依&#xff08;RuoYi&#xff09;框架&#xff0c;前端通过统一的 API 封装与后端进行数据交互&#xff0c;而后端再对接高仙官方的 OPE…

【第五节】部署http接口到ubuntu server上的docker内

描述清楚需求&#xff0c;让deepseek帮我们写一个demo&#xff0c;文件结构如下 FLASK_API_001 ├── app.py └── Dockerfile └── requirements.txtapp.pyfrom flask import Flask, jsonify, requestapp Flask(__name__)# 根路由 app.route(/) def home():return "…

在 IntelliJ IDEA 中添加框架支持的解决方案(没有出现Add Framework Support)

在 IntelliJ IDEA 中添加框架支持的解决方案 问题背景 版本变化&#xff1a;在 IntelliJ IDEA 2023.2 及更高版本中&#xff0c;项目右键菜单中的 “Add Framework Support” 选项已被移除。 常见需求&#xff1a;为 Java 项目添加框架支持&#xff08;如 Maven、Spring 等&am…

北京-4年功能测试2年空窗-报培训班学测开-第五十天

咦&#xff0c;昨天路上写一半就到家了&#xff0c;后来想早点睡就忘了还要发了&#xff0c;现在赶紧补上昨天是最后一节课(我们将一整天的课称为一节&#xff09;&#xff0c;这就结课了昨天讲了简历编写&#xff0c;面试要准备的内容&#xff0c;还有redis和docker也没有什么…

华为鸿蒙HarmonyOpenEye项目:开眼App的鸿蒙实现之旅

华为鸿蒙HarmonyOpenEye项目&#xff1a;开眼App的鸿蒙实现之旅 引言 在当今移动应用开发的浪潮中&#xff0c;鸿蒙系统凭借其独特的分布式能力和高效的开发框架&#xff0c;吸引了众多开发者的目光。今天要给大家介绍的是一个基于华为鸿蒙系统开发的开眼App项目——HarmonyO…

代码随想录day36dp4

文章目录1049.最后一块石头的重量II494.目标和474.一和零1049.最后一块石头的重量II 题目链接 文章讲解 class Solution { public:int lastStoneWeightII(vector<int>& stones) {// 1. 确定 DP 数组及下标的含义&#xff1a;// dp[i][j] 表示考虑前 i 块石头&#…

Python 爬虫实战指南:按关键字搜索商品

在电商领域&#xff0c;按关键字搜索商品并获取其详情信息是一项常见的需求。无论是进行市场调研、竞品分析还是用户体验优化&#xff0c;能够快速准确地获取商品信息都至关重要。1688 作为国内领先的 B2B 电商平台&#xff0c;提供了丰富的商品资源。本文将详细介绍如何使用 P…

【源力觉醒 创作者计划】百度AI的开放新篇章:文心4.5本地化部署指南与未来生态战略展望

百度AI的开放新篇章&#xff1a;文心4.5本地化部署指南与未来生态战略展望 一起来玩转文心大模型吧&#x1f449;文心大模型免费下载地址&#xff1a;https://ai.gitcode.com/theme/1939325484087291906 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30…

测试工作中的质量门禁管理

一、前言 测试阶段的质量门禁设计要考虑几个维度,首先是研发流程的阶段划分,每个阶段都要有明确的准入准出标准;其次要考虑不同测试类型的特点,比如功能测试和性能测试的验收标准肯定不同;最后还要平衡质量要求和项目进度。 在单元测试阶段,可以设置通过率和覆盖率的阈值…

线上分享:解码eVTOL安全基因,构建安全飞行生态

随着城市空中交通&#xff08;UAM&#xff09;快速发展&#xff0c;电动垂直起降飞行器&#xff08;eVTOL&#xff09;面临严格的安全与可靠性要求&#xff0c;需满足全球适航标准及全生命周期分析。安全与可靠的飞行系统成为行业关注的焦点。在此背景下&#xff0c;本期线上分…

C回调函数基础用法

&#x1f4cc; 定义&#xff1a;回调函数是通过函数指针传递给另一个函数的函数&#xff0c;这个被传进去的函数将在某个时刻被“回调”调用。换句话说&#xff1a;你定义一个函数 A把函数 A 的地址&#xff08;即函数指针&#xff09;作为参数传给函数 B函数 B 在合适的时机调…

手撕设计模式之消息推送系统——桥接模式

手撕设计模式之消息推送系统——桥接模式 1.业务需求 ​ 大家好&#xff0c;我是菠菜啊&#xff0c;好久不见&#xff0c;今天给大家带来的是——桥接模式。老规矩&#xff0c;在介绍这期内容前&#xff0c;我们先来看看这样的需求&#xff1a;我们现在要做一个消息推送系统&…

Java 大厂面试题 -- JVM 垃圾回收机制大揭秘:从原理到实战的全维度优化

最近佳作推荐&#xff1a; Java 大厂面试题 – JVM 面试题全解析&#xff1a;横扫大厂面试&#xff08;New&#xff09; Java 大厂面试题 – 从菜鸟到大神&#xff1a;JVM 实战技巧让你收获满满&#xff08;New&#xff09; Java 大厂面试题 – JVM 与云原生的完美融合&#xf…

图机器学习(9)——图正则化算法

图机器学习&#xff08;9&#xff09;——图正则化算法1. 图正则化方法2. 流形正则化与半监督嵌入3. 神经图学习4. Planetoid1. 图正则化方法 浅层嵌入方法已经证明&#xff0c;通过编码数据点间的拓扑关系可以构建更鲁棒的分类器来处理半监督任务。本质上&#xff0c;网络信息…

视频动态范围技术演进:从SDR到HDR的影像革命

一、动态范围技术基础认知 1.1 人眼视觉特性与动态范围 人眼的动态感知范围可达106:1&#xff08;0.0001-105 cd/m&#xff09;&#xff0c;远超传统显示设备能力。视网膜通过虹膜调节&#xff08;物理孔径&#xff09;与光化学反应&#xff08;光敏蛋白分解&#xff09;实现16…