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。 在单机/单服务器/单数据库的小型应用中,不需要用到这类东西。但在高并发、海量数据、大型分布式应用中,…...
计算机服务器中了勒索病毒怎么解决,勒索病毒解密流程,数据恢复
计算机服务器中了勒索病毒是一件非常令人头疼的事情,勒索病毒不仅会加密企业服务器中的数据,还会对企业计算机系统带来损害,严重地影响了企业的正常运转。最近,云天数据恢复中心工程师总结了,今年以来网络上流行的勒索…...
CMake实战:在Qt Creator中优雅集成第三方库的完整指南
1. 为什么需要优雅集成第三方库? 最近在做一个图像处理项目时,我遇到了一个典型问题:在本机调试一切正常,但把程序发给同事后却报错"找不到opencv_world450.dll"。这种问题在Windows平台开发中太常见了,根本…...
保姆级教程:OpenStack Rocky版Dashboard面板安装与配置避坑指南(附完整配置文件)
OpenStack Rocky版Dashboard深度配置指南:从原理到实战 第一次登录OpenStack Dashboard时,看到那个不断转圈的加载动画或者500错误页面,相信很多运维工程师都经历过这种挫败感。Dashboard作为OpenStack的门面,它的配置复杂度往往…...
手把手教你用网线搞定华为S5735S交换机堆叠(iStack实战避坑)
华为S5735S交换机零成本堆叠实战:用网线搭建高可靠网络 在中小企业网络升级过程中,端口扩展和链路冗余往往是刚需,但专用堆叠模块和光模块的高成本常常让预算有限的网管望而却步。华为S5735S系列交换机支持通过普通以太网电口(即R…...
明日方舟自动化助手MAA:从入门到精通的完整游戏辅助指南
明日方舟自动化助手MAA:从入门到精通的完整游戏辅助指南 【免费下载链接】MaaAssistantArknights 《明日方舟》小助手,全日常一键长草!| A one-click tool for the daily tasks of Arknights, supporting all clients. 项目地址: https://g…...
题解:AtCoder AT_awc0031_d Library Inventory Check
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来,并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构,旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。 欢迎大…...
2026 年 AI 应用开发学习路线:从入门到精通,6 个月速成实战指南
2026年,AI应用开发已从“技术尝鲜”迈入产业规模化落地的深水区,不再是单纯的模型API调用,而是转向RAG企业知识库、AI Agent智能体、多模态交互、私有化部署等高价值场景。对于开发者、转行程序员、零基础小白而言,今年的学习核心…...
从微波炉变压器到精密焊接:详解DIY点焊机中‘自动触发笔’的工作原理与升级方案
从微波炉变压器到精密焊接:详解DIY点焊机中‘自动触发笔’的工作原理与升级方案 在业余电子制作和小规模金属加工中,点焊机因其高效、低成本的特性成为不可或缺的工具。许多DIY爱好者会选择改造废旧微波炉变压器来制作简易点焊机,但往往忽视了…...
如何快速掌握Steam成就管理:SteamAchievementManager终极实战指南
如何快速掌握Steam成就管理:SteamAchievementManager终极实战指南 【免费下载链接】SteamAchievementManager A manager for game achievements in Steam. 项目地址: https://gitcode.com/gh_mirrors/st/SteamAchievementManager SteamAchievementManager&am…...
终极指南:5个快速解决Ryujinx模拟器常见问题的完整教程
终极指南:5个快速解决Ryujinx模拟器常见问题的完整教程 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx Ryujinx是一款用C#编写的开源Nintendo Switch模拟器,致力…...
手把手用GD32F307C-EVAL板调试Timer0互补PWM(含死区与刹车功能)
基于GD32F307C-EVAL实现高级定时器互补PWM全流程实战 最近在电机控制项目中尝试使用GD32F307的高级定时器功能,发现其互补PWM输出配合死区时间与刹车保护的组合应用,能显著提升系统可靠性。本文将用开发板上的TIMER0为例,演示从硬件连接到波形…...
