Leetcode1839. 所有元音按顺序排布的最长子字符串
Every day a Leetcode
题目来源:1839. 所有元音按顺序排布的最长子字符串
解法1:滑动窗口
要找的是最长美丽子字符串的长度,我们可以用滑动窗口解决。
设窗口内的子字符串为 window,每当 word[right] >= window.back() 时,说明可以按字典序升序排布,我们都可以将 word[right] 添加进 window 的末尾,我们使用一个集合 cnt 存储每次遇到的 word[right],当 cnt.size() = 5时,说明所有 5 个英文元音字母都至少出现了一次,更新长度:max_len = max(max_len, (int)window.size())。
如果遇到了不按字典序升序排布的情况,我们发现窗口必须全部清空,于是有:window = “”,cnt.clear(),同时要改变窗口的左边界 left = right,立即将 word[left] 加入进窗口和集合,重新开始遍历。
代码:
/** @lc app=leetcode.cn id=1839 lang=cpp** [1839] 所有元音按顺序排布的最长子字符串*/// @lc code=start// 滑动窗口class Solution
{
public:int longestBeautifulSubstring(string word){// 特判if (word.size() < 5)return 0;int n = word.size();string window;unordered_set<char> cnt;int max_len = 0, left = 0, right = 0;while (right < n){if (window.empty() || word[right] >= window.back()){window += word[right];cnt.insert(word[right]);right++;if (cnt.size() == 5)max_len = max(max_len, (int)window.size());}else{window = "";cnt.clear();left = right;window += word[left];cnt.insert(word[left]);right++;}}return max_len;}
};
// @lc code=end
结果:

复杂度分析:
时间复杂度:O(n),其中 n 是字符串 word 的长度。
空间复杂度:O(n),其中 n 是字符串 word 的长度。
解法2:一次遍历
由滑动窗口的启发,我们发现只设立几个变量也能达到相同的效果。
代码:
class Solution
{
public:int longestBeautifulSubstring(string word){// 特判if (word.size() < 5)return 0;int n = word.size();int max_len = 0;int vowel = 1, cur_len = 1;for (int i = 1; i < n; i++){if (word[i] >= word[i - 1]){cur_len++;if (word[i] > word[i - 1])vowel++;}else{cur_len = 1;vowel = 1;}if (vowel == 5)max_len = max(max_len, cur_len);}return max_len;}
};
结果:

复杂度分析:
时间复杂度:O(n),其中 n 是字符串 word 的长度。
空间复杂度:O(1)。
相关文章:
Leetcode1839. 所有元音按顺序排布的最长子字符串
Every day a Leetcode 题目来源:1839. 所有元音按顺序排布的最长子字符串 解法1:滑动窗口 要找的是最长美丽子字符串的长度,我们可以用滑动窗口解决。 设窗口内的子字符串为 window,每当 word[right] > window.back() 时&…...
C/C++程序设计和预处理
个人主页:仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏:C语言疑难_仍有未知等待探索的博客-CSDN博客 目录 一、引言 二、程序的翻译环境和执行环境 1、什么是程序 2、程序的翻译环境 3、程序的执行环境 三、预处理 1、预定义符…...
openssl生成自签名证书
原网址:https://blog.csdn.net/weixin_41767181/article/details/121531007 windows下安装openssl后,生成自签名证书并打包为P12文件的命令如下: 需要注意的是: 每一级的证书中,证书的公司名称等尽量不要一样根证书…...
JAVA毕业设计100—基于Java+Springboot+Vue的WMS仓库管理系统+移动端微信小程序(源码+数据库+部署视频)
基于JavaSpringbootVue的WMS仓库管理系统移动端(源码数据库部署视频) 一、系统介绍 本系统前后端分离带小程序 本系统分为管理员、用户角色(角色权限可自行分配) 功能列表: 1、 数据管理:物料数据管理、物料Bom管理、物料组管理、物料分类管理、供应…...
深度学习推荐系统架构、Sparrow RecSys项目及深度学习基础知识
文章目录 🌟 技术架构:深度学习推荐系统的经典技术架构长啥样?🍊 一、深度学习推荐系统的技术架构🍊 二、基于用户行为的推荐🍊 三、基于多模态数据的推荐🍊 四、基于知识图谱的推荐 dz…...
ios UI 基础开发二
第一节:UIPickerView、UIPickerViewDataSource、UIPickerViewDelegate 设置约束,如果要设置两个兄弟的约束,可以按住option键,用鼠标右键把a拖到b上面,表示a按照b来对齐 生成随机数 如果后面列的数据,依赖前…...
失配树学习笔记
失配树,是一种奇妙的数据结构,它利用 KMP、LCA 解决求两前缀的最长公共 Border 的问题。 首先介绍一下什么是 Border,我们知道 nxt 数组是前后缀相同的最大长度,Border 相当于是 nxt 数组的弱化版,只是去掉了“最大”…...
【Electron】Not allowed to load local resource
问题描述 使用 audio 标签播放音频文件,控制台报错 Not allowed to load local resource。 Not allowed to load local resource原因分析 通常是安全策略所引起的。Electron 默认情况下禁止加载本地资源,以防止潜在的安全风险。 解决方案 在 main.js…...
Maven 基础教程系列
Maven是一个项目开发管理和理解工具。基于项目对象模型的概念:构建、依赖关系管理、文档创建、站点发布和分发发布都由pom.xml声明性文件控制。Maven可以通过插件进行扩展,以使用许多其他开发工具来报告或构建过程。 一、Maven 使用教程-CSDN博客 二、…...
c++之类和对象
1.auto 可以自动推导结果的类型 typeid()可以打印类型 引用也可以 auto真正的价值可以简化迭代器的写法 并且auto定义的变量必须初始化。 不能做参数 返回值也不可以用auto auto不能用来声明数组 如果想要修改要用引用且指针不好解决。 c11之后的nullptr 以后再用空指针用nul…...
分布式应用开发的核心技术系列之——基于TCP/IP的原始消息设计
本文由葡萄城技术团队原创并首发。转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。 前言 本文的内容主要围绕以下几个部分: TCP/IP的简单介绍。消息的介绍。基于消息分类的传输格式&…...
医疗领域的数字化浪潮:互联网医院平台的关键作用
数字化浪潮正在迅速改变医疗领域的方式和效率。互联网医院平台作为数字化医疗的关键元素,正在为医疗行业带来巨大的变革。本文将探讨互联网医院平台的关键作用,并提供一个示例,使用Python编写一个简单的医疗预约系统。 互联网医院平台的关键…...
将本地的项目上传到Gitee
目录 1.先在Gitee新建一个仓库,提交即可 2.进入到要上传的项目里面,右键选择 Git Bash Here 3.右键后就打开了Git命令窗口 4.配置你的用户名和邮箱(已经配置过则可跳过) 5.查看你的用户名和邮箱配置(可不查看) 6.输入git init指令&#…...
概率论_概率公式中的分号(;)、逗号(,)、竖线(|)
1. 概率公式中的分号(;)、逗号(,)、竖线(|) ; 分号代表前后是两类东西,以概率P(x;θ)为例,分号前面是x样本,分号后边是模型参数。 , 逗号代表两者地位平等,代表与的关系 | 竖线代表 if,一上面为例,就是如果…...
Spark Streaming 整合 Kafka
本文代码链接:https://download.csdn.net/download/shangjg03/88442308 1.版本说明 Spark 针对 Kafka 的不同版本,提供了两套整合方案:`spark-streaming-kafka-0-8` 和 `spark-streaming-kafka-0-10`,其主要区别如下: 本文使用的 Kafka 版本为 `kafka_2.12-2.2.0`,故采用…...
【API篇】五、Flink分流合流API
文章目录 1、filter算子实现分流2、分流:使用侧输出流3、合流:union4、合流:connect5、connect案例 分流,很形象的一个词,就像一条大河,遇到岸边有分叉的,而形成了主流和测流。对于数据流也一样…...
flutter开发的一个小小小问题,内网依赖下不来
问题 由于众所周知的原因,flutter编译时,经常出现Could not get resource https://storage.googleapis.com/download.flutter.io…的问题,如下: * What went wrong: Could not determine the dependencies of task :app:lintVit…...
RabbitMQ队列及交换机的使用
目录 一、简单模型 1、首先控制台创建一个队列 2、父工程导入依赖 3、生产者配置文件 4、写测试类 5、消费者配置文件 6、消费者接收消息 二、WorkQueues模型 1、在控制台创建一个新的队列 2、生产者生产消息 3、创建两个消费者接收消息 4、能者多劳充分利用每一个消…...
分布式唯一Id,它比GUID好
分布式唯一Id,它比GUID好 一、前言 分布式唯一Id,顾名思义,是指在全世界任何一台计算机上都不会重复的唯一Id。 在单机/单服务器/单数据库的小型应用中,不需要用到这类东西。但在高并发、海量数据、大型分布式应用中,…...
计算机服务器中了勒索病毒怎么解决,勒索病毒解密流程,数据恢复
计算机服务器中了勒索病毒是一件非常令人头疼的事情,勒索病毒不仅会加密企业服务器中的数据,还会对企业计算机系统带来损害,严重地影响了企业的正常运转。最近,云天数据恢复中心工程师总结了,今年以来网络上流行的勒索…...
工业大数据如何驱动制造业智能化升级?核心应用与案例解析
一、当预测不再是拍脑袋——工业大数据的觉醒时刻系统算出下月销量500台,计划员说不清依据,总监因下月有大促随手改成600台。这个在制造、零售、快消行业反复上演的场景,像一面镜子照出传统工业数据应用的尴尬:数据有了࿰…...
2026实用论文降AI工具盘点:含免费版高效去AI痕迹方案
写论文的苦谁懂?熬了几个通宵赶出来的稿子,要么查重飘红一片,要么AI检测直接标红高危,改到凌晨三点还是过不了关。 为了搞定论文降AIGC,我前前后后踩了不下二十个坑,试了市面上几十款降AI率工具,有的改完逻辑混乱像小学生写的,有的AI率没降反而升了,还有的直接把我论…...
别再只用EEMD了!CEEMDAN在MATLAB里这么用,信号分解又快又准
CEEMDAN在MATLAB中的高效信号分解实战指南 从EEMD到CEEMDAN的技术跃迁 信号分解领域正在经历一场静悄悄的革命。五年前,EEMD(集合经验模态分解)还是处理非平稳信号的黄金标准,但今天,越来越多的工程师发现他们的工具箱…...
5步搞定明日方舟全自动化:MAA助手终极指南
5步搞定明日方舟全自动化:MAA助手终极指南 【免费下载链接】MaaAssistantArknights 《明日方舟》小助手,全日常一键长草!| A one-click tool for the daily tasks of Arknights, supporting all clients. 项目地址: https://gitcode.com/Gi…...
Hyperf方案 服务依赖分析与治理
Hyperf 服务依赖分析与治理,核心工具链:┌──────────────┬──────────────────────────────────┐│ 关注点 │ 方案 │ …...
Skyeye云智能制造v3.19.2发布:零代码平台,功能升级,开发效率大提升!
【Skyeye云智能制造简介】Skyeye云智能制造是智能制造一体化,采用SpringBoot UNI - APP Ant Design Vue的零代码平台开发模式。它包含100多种电子流程,以及CRM、PM、ERP、MES、ADM、OA、EHR、AI、项目、商城、财务、多班次考勤、薪资、招聘、云售后、论…...
Pybind11实战:在Visual Studio里为你的C++算法快速生成Python接口
Pybind11实战:在Visual Studio里为你的C算法快速生成Python接口 当你的C算法需要被Python开发者调用时,Pybind11就像一座高效的桥梁。这个轻量级库能让你用几行代码就把复杂的C函数暴露给Python,省去了传统扩展开发的繁琐流程。想象一下&…...
零成本实现单机分屏:Nucleus Co-Op让一台电脑变多人游戏主机
零成本实现单机分屏:Nucleus Co-Op让一台电脑变多人游戏主机 【免费下载链接】nucleuscoop Starts multiple instances of a game for split-screen multiplayer gaming! 项目地址: https://gitcode.com/gh_mirrors/nu/nucleuscoop 还在为朋友聚会时电脑不够…...
SiameseUIE模型在网络安全领域的应用:威胁情报抽取
SiameseUIE模型在网络安全领域的应用:威胁情报抽取 网络安全分析师每天都要面对海量的威胁情报报告、安全日志和漏洞公告。这些文本数据里藏着攻击者的IP地址、恶意域名、攻击手法、漏洞编号等关键信息。传统做法是人工逐篇阅读、标记、整理,不仅效率低…...
HLS流媒体下载器技术实现:并发处理与AES解密优化策略
HLS流媒体下载器技术实现:并发处理与AES解密优化策略 【免费下载链接】m3u8_downloader 项目地址: https://gitcode.com/gh_mirrors/m3/m3u8_downloader 在数字媒体内容日益丰富的今天,HLS(HTTP Live Streaming)已成为视频…...
