(滑动窗口) 76. 最小覆盖子串 ——【Leetcode每日一题】
❓76. 最小覆盖子串
难度:困难
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2:
输入:s = “a”, t = “a”
输出:“a”
解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
m == s.length
n == t.length
- 1 < = m , n < = 1 0 5 1 <= m, n <= 10^5 1<=m,n<=105
s
和t
由英文字母组成
进阶:你能设计一个在 O ( m + n ) O(m+n) O(m+n) 时间 内解决此问题的算法吗?
💡思路:滑动窗口
滑动窗口的思想:
用l
和r
表示滑动窗口的左边界和 右边界,通过改变l
,r
来 扩展 和 收缩 滑动窗口,可以想象成一个窗口在字符串上游走,当这个窗口包含的元素满足条件,即包含字符串t
的所有元素,记录下这个滑动窗口的长度r - l +1
,这些长度中的最小值就是要求的结果。
由于 t
可能包含 重复字符 ,所以使用哈希表 ori
记录 t
中所有的字符以及它们的个数;使用另一个哈希表 cnt
动态维护窗口中所有的字符以及它们的个数。
如果 当前窗口 中包含 t
中所有的字符,且对应的字符个数都不小于 t
的哈希表中各个字符的个数,则当前窗口是「可行」的。此时左边界 l
右移,直到不涵盖 t
中的所有字符,上一个即为满足条件的 当前窗口的最小子串。
使用 distance
记录 当前窗口 中字符 属于 t
对应的个数;当 cnt[s[r]] < ori[s[r]]
时,每增加一个 s[r]
, distance ++
,否则 distance
不变。 同理 当 cnt[s[l]] <= ori[s[l]]
每减少一个 s[l]
, distance --
,否则 distance
不变。(这样可以在 O ( 1 ) O(1) O(1) 的复杂度判断 当前窗口 内的字符是否符合要求)
具体步骤如下:
- 不断增加
r
使滑动窗口 增大,直到窗口包含了t
的所有元素; - 不断增加
l
使滑动窗口 缩小,因为是要求最小字串,所以将不必要的元素排除在外,使长度减小,直到碰到一个必须包含的元素,这个时候不能再扔了,再扔就不满足条件了,记录此时滑动窗口的长度,并保存最小值; - 让
l
再增加一个位置,这个时候滑动窗口肯定不满足条件了,那么继续从 步骤 1 开始执行,寻找新的满足条件的滑动窗口,如此反复,直到r
超出了字符串s
范围。
🍁代码:(C++、Java)
C++
class Solution {
public:unordered_map <char, int> ori, cnt;string minWindow(string s, string t) {for(const auto &c : t){ //使用哈希表记录t中所有的字符,及其对应的个数++ori[c];}int l = 0, r = -1;int len = INT_MAX, ansl = -1;int distance = 0;while(r < int(s.size())){if(ori.find(s[++r]) != ori.end() && ++cnt[s[r]] <= ori[s[r]] ){//对任何属于t的字符都记录distance++;//记录当前窗口的子串中属于t的字符的个数}while(distance == t.size() && l <= r){//包括所有字符,左指针右移if(r - l + 1 < len){//更新结果len = r - l + 1;ansl = l;}if(ori.find(s[l]) != ori.end() && --cnt[s[l]] < ori[s[l]]){distance--;}++l;}}return ansl == -1 ? string() : s.substr(ansl, len);}
};
Java
class Solution {Map<Character, Integer> ori = new HashMap<Character, Integer>();Map<Character, Integer> cnt = new HashMap<Character, Integer>();public String minWindow(String s, String t) {for(int i = 0; i < t.length(); i++){//使用哈希表记录t中所有的字符,及其对应的个数char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = -1;int len = Integer.MAX_VALUE, ansl = -1;int distance = 0;while(++r < s.length()){char c = s.charAt(r);if(ori.containsKey(c)){//对任何属于t的字符都记录cnt.put(c, cnt.getOrDefault(c, 0) + 1);if(cnt.get(c) <= ori.get(c)){//记录当前窗口的子串中属于t的字符的个数distance++;}}while(distance == t.length() && l <= r){if(r - l + 1 < len){//更新结果len = r - l + 1;ansl = l;}if(ori.containsKey(s.charAt(l))){cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);if(cnt.get(s.charAt(l)) < ori.get(s.charAt(l))){distance--;}}++l;}}return ansl == -1 ? "" : s.substring(ansl, ansl + len);}
}
🚀 运行结果:
🕔 复杂度分析:
- 时间复杂度: O ( ∣ s ∣ + ∣ t ∣ ) O(∣s∣+∣t∣) O(∣s∣+∣t∣),最坏情况下左右指针对
s
的每个元素各遍历一遍,哈希表中对s
中的每个元素各插入、删除一次,对t
中的元素各插入一次。 - 空间复杂度: O ( C ) O(C) O(C),这里用了两张哈希表作为辅助空间,每张哈希表最多不会存放超过字符集大小的键值对,我们设字符集大小为
C
,则渐进空间复杂度为 O ( C ) O(C) O(C)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:

(滑动窗口) 76. 最小覆盖子串 ——【Leetcode每日一题】
❓76. 最小覆盖子串 难度:困难 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 注意: 对于 t 中重复字符,我们寻找的子字符串…...
grep批量筛选指定目录下的所有日志并写入文件内
背景:在指定目录下,该目录下有上百个日志文件,这些文件以.log结尾 需求:遍历这些日志文件,对每个日志文件进行grep筛选,筛选出包含namexxx和 "server_port":"8088"的内容,并…...

JVM第三讲:JVM 基础-字节码的增强技术详解
JVM 基础-字节码的增强技术详解 本文是JVM第三讲,JVM 基础-字节码的增强技术。在上文中,着重介绍了字节码的结构,这为我们了解字节码增强技术的实现打下了基础。字节码增强技术就是一类对现有字节码进行修改或者动态生成全新字节码文件的技术…...

JWT前后端分离在项目中的应用
14天阅读挑战赛当你累了,要学会休息,而不是放弃! 目录 一、JWT简介 1.1 什么是JWT 1.2 为什么要使用JWT,与session的区别 1.3 JWT组成及工作原理和流程 二、JWT工具类解析 2.1 生成JWT 2.2 解析oldJwt 2.3 复制JWT并延时…...
系统架构师备考倒计时23天(每日知识点)Redis篇
Redis篇 1.Redis与Memcache能力对比 工作MemCacheRedis数据类型简单 key/value 结构丰富的数据结构持久性不支持支持分布式存储客户端哈希分片/一致性哈希多种方式,主从、Sentinel、Cluster 等多线程支持支持支持(Redis5.0及以前版本不支持)内存管理私有内存池/内…...

WIN11系统设置重启与睡眠唤醒后自动拨号
文章目录 1. win x快捷键后选择计算机管理2. 编辑名称3. 选择计算机启动时4. 启动程序5. 输入脚本6. 勾选选项7. 填写配置8. 新建触发器9. 设置触发器10. 确定之后完成创建 1. win x快捷键后选择计算机管理 在任务计划程序中创建基本任务 2. 编辑名称 3. 选择计算机启动时 4…...

【【萌新的SOC学习之AXI-DMA环路测试】】
萌新的SOC学习之AXI-DMA环路测试 AXI DMA环路测试 DMA(Direct Memory Access,直接存储器访问)是计算机科学中的一种内存访问技术。它允许某些计算机内部的硬件子系统可以独立地直接读写系统内存,而不需中央处理器(CPU)介入处理。…...
Lua教程
Lua教程(简单易懂)-CSDN博客 博客相关解释: 5、循环 a {"a", "b"}for i, v in ipairs(a) doprint(i, v)end 代码创建了一个名为 a 的数组,并使用 ipairs 迭代这个数组的元素。运行结果显示了每个元素的索引(下标&am…...

《Node.js+Express+MongoDB+Vue.js全栈开发实战》简介
今天介绍的这本书是《Node.jsExpressMongoDBVue.js全栈开发实战》。该书由清华大学出版社于2023年1月出版 外观 从书名故名思议,就是基于Node.jsExpressMongoDBVue.js来实现企业级应用全栈开发。 封面风格比较简约,插图是一张类似于罗马时代战车形象&…...

多输入多输出 | MATLAB实现CNN-BiGRU-Attention卷积神经网络-双向门控循环单元结合SE注意力机制的多输入多输出预测
多输入多输出 | MATLAB实现CNN-BiGRU-Attention卷积神经网络-双向门控循环单元结合SE注意力机制的多输入多输出预测 目录 多输入多输出 | MATLAB实现CNN-BiGRU-Attention卷积神经网络-双向门控循环单元结合SE注意力机制的多输入多输出预测预测效果基本介绍程序设计往期精彩参考…...

阿里云r7服务器内存型CPU采用
阿里云服务器ECS内存型r7实例是第七代内存型实例规格族,CPU采用第三代Intel Xeon可扩展处理器(Ice Lake),基频2.7 GHz,全核睿频3.5 GHz,计算性能稳定,CPU内存比1:8,2核16G起步&#…...

Godot2D角色导航-自动寻路教程(Godot设置导航代理的目标位置)
文章目录 创建导航NavigationAgent2D节点设置目标位置其他文章 创建导航 首先,创建一个基本的场景,下面的文章讲解了如何创建一个基本的导航场景,点击如下链接前往该文章: Godot2D角色导航-自动寻路教程 NavigationAgent2D节点 …...

R语言实现向量自回归和误差修正模型——附实战代码
大家好,我是带我去滑雪! 向量自回归(VAR)模型和误差修正模型(ECM)是时间序列分析中常用的两种模型,它们用于研究多个变量之间的动态关系。VAR 模型适用于研究多个相关变量之间的相互影响和动态关…...

原理:用UE5制作一个2D游戏
选中资产图片右键--Sprite Actions--Apply Paper2D Texture Settings 制作场景 把它丢到场景里,并把坐标归零 创建图块集tileset 打开新建的tile set,根据最小图块设置最小尺寸单元 选择需要的图块单元,add box 对新建的tile set右键创建til…...
【ARM 嵌入式 编译系列 11.3 -- GCC attribute packed noreturn constructor 介绍】
文章目录 GCC 的 __attribute__ 是一个编译器扩展特性,允许开发者在源代码中设置函数属性(function attributes)、变量属性(variable attributes)和类型属性(type attributes)。这些属性可以影响函数、变量或类型的行为。 以下是一些常见的 __attribute__ 属性: __at…...

主从Reactor高并发服务器
文章目录 Reactor模型的典型分类单Reactor单线程单Reactor多线程多Reactor多线程本项目中实现的主从Reactor One Thread One Loop各模型的优点与缺点 项目分解Reactor服务器模块BufferSocketChannelEpollerTimerWheelEventLoopAnyConnectionAcceptorLoopThreadLoopThreadPoolTc…...

文心一言Plugin实战来了,测试开发旅游攻略助手
刚刚过去的8月,百度WAVE SUMMIT 深度学习开发者大会上,重磅发布文心一言的五个原生插件:百度搜索、览卷文档(基于文档的交互)、E 言易图(数据洞察图表生成)、说图解画(基于图片的交互…...

微服务13-Seata的四种分布式事务模式
文章目录 XA模式实现XA模式 AT模式AT模式的脏写问题(对同数据并发写的问题)其他事务不获取全局锁的一个情况(AT模式写隔离的实现)实现AT模式 TCC模式TCC实现我们怎么样去判断是否空回滚和业务悬挂?业务分析 Saga模式总…...

C结构体内定义结构体,不能直接赋值。
现像: 如下代码: 头文件: typedef struct aBlinkGpioPinOutAbst_{void (*initAsOutput)(void);void (*high)(void);void (*low)(void); }aBlinkGpioPinOutAbst;typedef struct aBlinkGpioAbst_{ #if GPIO_CONFIG_PA0 GPIO_CONFIG_AS_OUTPU…...

PHP遇见错误了看不懂?这些错误提示你必须搞懂
🎬 鸽芷咕:个人主页 🔥 个人专栏:《速学数据结构》 《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活! 文章目录 一、错误分类二、系统错误:2.1 编译错误2.2 致命错误2.3 警告错误2.4 通知错误 三、用户错误3.1 错…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...