首页 > 其他分享 >LeetCode76. 最小覆盖子串(2024秋季每日一题 14)

LeetCode76. 最小覆盖子串(2024秋季每日一题 14)

时间:2024-09-14 15:26:19浏览次数:13  
标签:子串 字符 LeetCode76 14 覆盖 int dif 2024 字符串


给你一个字符串 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 的子串中,
因此没有符合条件的子字符串,返回空字符串。

提示:

LeetCode76. 最小覆盖子串(2024秋季每日一题 14)_双指针
LeetCode76. 最小覆盖子串(2024秋季每日一题 14)_哈希表_02
LeetCode76. 最小覆盖子串(2024秋季每日一题 14)_leetcode_03
s 和 t 由英文字母组成

进阶:你能设计一个在 LeetCode76. 最小覆盖子串(2024秋季每日一题 14)_双指针_04


思路:双指针 + 哈希表

  • 通过哈希表记录 t 串每个字符出现的次数
  • dif 记录(当前子串,距离覆盖 t 串)差多少个覆盖字符(对于覆盖的字符,必须满足,c 属于t,并且c属于子串,并且子串的sub_cnt[c] >= t_cnt[c] )
  • r 是子串的区间右边界,l 是子串的左边界
  • 假如当前子串没有覆盖 t 串,则 r 右移,直到覆盖
  • 假如当前子串覆盖,则 l 右移,找出最小的覆盖串

LeetCode76. 最小覆盖子串(2024秋季每日一题 14)_leetcode_05

时间复杂度:LeetCode76. 最小覆盖子串(2024秋季每日一题 14)_滑动窗口_06

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> h;
        int dif = t.size();
        for(int i = 0; i < t.size(); i++) h[t[i]]++;
        string res = "";
        int start = 0, end = -1;
        int l = 0, r = -1;
        int n = s.size();
        for(int r = 0; r < n; r++){
            if(h.count(s[r])){
                if(h[s[r]] > 0) dif--;
                h[s[r]]--;
            }
            
            while(dif == 0 && l <= r){
                if(end == -1) start = l, end = r;
                else if((r - l) < (end - start)){
                    start = l, end = r;
                }
                l++;
                if(h.count(s[l - 1])) {
                    h[s[l-1]]++;
                    if(h[s[l-1]] >= 1) dif++;
                }
            }
        }
        if(end != -1) res = s.substr(start, end - start + 1);
        return res;
    }
};


标签:子串,字符,LeetCode76,14,覆盖,int,dif,2024,字符串
From: https://blog.51cto.com/u_15236041/12017083

相关文章

  • LeetCode239. 滑动窗口最大值(2024秋季每日一题 13)
    给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例1:输入:nums=[1,3,-1,-3,5,3,6,7],k=3输出:[3,3,5,5,6,7]解释:示例2:输入:nums=[1],k......
  • 2024年图纸加密软件最新版排行榜出炉!10款图纸加密软件大比拼
    随着企业和个人对信息安全的关注日益增加,图纸加密软件成为了保护机密数据的重要工具。无论是工程设计公司、建筑公司,还是制造业,都需要确保图纸文件的安全性,防止未经授权的访问和泄漏。2024年,一系列全新功能和技术的图纸加密软件登上了排行榜。本文将为您详细介绍排名前十的图......
  • 企业源代码怎么加密防泄密?2024十款好用的源代码加密软件
    在当今数字化和信息化的时代,企业的源代码通常承载了核心技术和商业机密,若被泄露或窃取,可能导致企业遭受不可估量的损失。为防止源代码泄密,企业需要采取多层次的安全措施,其中源代码加密是最关键的一环。1.安秉源代码加密安秉源代码加密软件是一款适用于Windows和Linux平台的......
  • 2024年PMP我可以自学通过考试吗?
    作为PMP考试的老考生,我想提醒一下,PMP考试费用很高,初次考试费用为3900元(重考费用为2500元)。如果你想自学PMP,一定要三思而后行。首先要问问自己是否符合以下几种情况:1.有相关的工作经验(项目经理/产品经理/技术岗),对项目管理的工作流程比较熟悉,这是一个优势。2.0基础,但学习能力......
  • springboot仓库仓储管理系统-计算机毕业设计源码14514
    目录1绪论1.1选题背景与意义1.2国内外研究现状1.3论文结构与章节安排2系统分析2.1可行性分析2.1.1技术可行性2.1.2经济可行性2.1.3操作可行性2.1.4法律可行性2.2系统流程分析2.2.1系统开发流程2.2.2用户登录流程2.2.3系统操作流程2.2.4......
  • 2024.9.12(周四)
    hadoop实现后台修改importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.hbase.HBaseConfiguration;importorg.apache.hadoop.hbase.TableName;importorg.apache.hadoop.hbase.client.Connection;importorg.apache.hadoop.hbase.client.ConnectionFac......
  • 2024远程办公快速崛起,ToDesk抢先拿下上亿设备
    自2020年以来,在疫情影响下,远程办公正在进一步常态化渗透到各类企业中。根据公开数据,腾讯会议、飞书等线上协同软件月度活跃用户已突破千万级别,一场围绕”办公空间“的变革正在发生。在小编看来,远程移动办公给予企业和打工人更多机遇和挑战。对互联网软件企业而言,远程移动办公不......
  • 2024.9.11(周三)
    packagehadoop;importjava.io.IOException;importjava.util.StringTokenizer;importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.fs.Path;importorg.apache.hadoop.io.IntWritable;importorg.apache.hadoop.io.Text;importorg.apache.hado......
  • 北京2024年下半年软考准考证打印时间11月5日开始
    根据2024下半年北京软考考务通知的说明,2024下半年北京软考准考证打印相关事项如下:一、2024下半年北京软考准考证打印时间2024年11月5日至11月8日。二、2024下半年北京软考准考证打印入口网址考生登录中国计算机技术职业资格网网上报名系统(http://www.ruankao.org.cn/),点击链接进入......
  • 2024.09.14模拟赛总结
    $T1$似乎是签到题,但是没开$unsigned$$long$$long$挂成$88$分了。直接模拟即可,从后往前考虑,将每个数放到离其最近的位置,不过不会证...#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongLL;constintN=1000010;structwasd......