开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

具有原始字符串所有不同字符的最小长度子串的滑动窗口解决方案

滑动窗口是一种常用的算法技巧，用于解决字符串或数组的子串/子数组问题。它通过维护一个窗口，根据问题的要求移动窗口的起始位置和结束位置，从而找到满足条件的子串/子数组。

对于具有原始字符串所有不同字符的最小长度子串的问题，可以使用滑动窗口解决方案来解决。以下是一个完善且全面的答案：

滑动窗口解决方案：

初始化一个空的窗口，用两个指针start和end表示窗口的起始位置和结束位置。
将end指针向右移动，直到窗口中包含了原始字符串的所有不同字符。
记录当前窗口的长度和起始位置，作为当前的最小长度子串。
将start指针向右移动，缩小窗口的大小，直到窗口中不再包含原始字符串的所有不同字符。
重复步骤2到步骤4，直到end指针到达字符串的末尾。
返回最小长度子串的长度和起始位置。

滑动窗口解决方案的优势：

时间复杂度为O(n)，其中n是字符串的长度。滑动窗口只需要遍历一次字符串。
空间复杂度为O(k)，其中k是原始字符串中不同字符的数量。滑动窗口需要维护一个哈希表来记录窗口中的字符及其出现次数。

滑动窗口解决方案的应用场景：

字符串中找到包含所有指定字符的最短子串。
数组中找到包含所有指定元素的最短子数组。
字符串中找到最长的无重复字符子串。

腾讯云相关产品和产品介绍链接地址：

腾讯云云服务器（CVM）：https://cloud.tencent.com/product/cvm
腾讯云云数据库MySQL版：https://cloud.tencent.com/product/cdb_mysql
腾讯云云原生容器服务（TKE）：https://cloud.tencent.com/product/tke
腾讯云云存储（COS）：https://cloud.tencent.com/product/cos
腾讯云人工智能（AI）：https://cloud.tencent.com/product/ai
腾讯云物联网（IoT）：https://cloud.tencent.com/product/iotexplorer
腾讯云移动开发（移动推送、移动分析）：https://cloud.tencent.com/product/mpns
腾讯云区块链（BCS）：https://cloud.tencent.com/product/bcs
腾讯云元宇宙（Tencent Cloud Metaverse）：https://cloud.tencent.com/solution/metaverse

请注意，以上链接仅供参考，具体的产品选择应根据实际需求和情况进行评估和选择。

相关搜索:包含所有字母的不同字符的最短子字符串的长度可以连接成R中的原始字符串的所有子字符串组合在typescript中声明具有最小/最大长度的字符串类型使用yield生成给定长度的所有子字符串不同长度的字符串排列拆分不同长度的字符串查找固定长度字符串的所有可能的子序列查找字符串中具有最大长度的所有单词从不同长度的字符串中获取特定长度的字符串字符串的最小长度，以C为单位打印给定字符串的所有子字符串的程序返回重复子字符串的长度获取JavaScript中字符串的所有子字符串具有某些性质的最小字符串拆分长度和字符不同的字符串在不同长度的字符串中查找不同的字符匹配不同长度的字符串前缀处理不同长度的日期字符串具有重复子字符串的Perl重复字符串无法提取具有子字符串中变量的字符串

相关搜索:

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

01

【算法专题】滑动窗口

找出该数组中满足其和 ≥ target 的长度最小的连续子数组[numsl, numsl + 1, …, numsr - 1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

01

三分钟算法修行-无重复字符的最长子串的《四种解法》

最近有小伙伴和我谈心，觉得刷算法题太难了，完全没有思路，很有挫败感，想要放弃了。想想自己也深有感触，有这些想法真都挺正常的，其实我们刷算法就是为了培养一个思考问题、解决问题的思维，这个思维养成并不是一蹴而就的，而是循序渐进的。

02

leetcode必备算法：聊聊滑动窗口

我们刷leetcode的时候，经常会遇到滑动窗口类型题目。滑动窗口问题非常经典，也很有技巧性，一般大厂也喜欢问。今天跟大家一起来学习滑动窗口的套路，文章如果有不正确的地方，欢迎大家指出哈，感谢感谢~

04

LeetCode每日一练（无重复字符的最长子串）

题目要求找出给定字符串中不含重复字符的最长子串，我们可以采用暴力穷举的方式，得到字符串中的所有子串，然后一一判断不重复子串的长度，最后返回最长子串的长度即可，比如：

02

【JavaScript 算法】滑动窗口：处理子数组问题

滑动窗口算法通过在数组上维护一个窗口来解决子数组问题。窗口的大小和位置可以动态调整，以满足不同问题的需求。滑动窗口的基本思想是：

01

滑动窗口算法的基本思想、应用场景、实现方法、时间复杂度和常见问题

滑动窗口算法（Sliding Window）是一种常用的双指针算法，被广泛应用于字符串和数组等数据结构中的子串或子数组问题，例如字符串匹配、最长子串、最小覆盖子串等问题。滑动窗口算法可以优化暴力枚举的时间复杂度，使得算法的执行效率更高。

00

七十四、滑动窗口最值问题

滑动问题包含一个滑动窗口，它是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。一般用来求最值问题。

02

双指针滑动窗口法解析及LeetCode相关题解

如下图，n=8,k=3，即求连续3个数和的最大值。可以想象有一个红色的容量为3个数字的矩形窗口在沿着数字序列滑动，有两个指针right和left分别指向窗口的两端：left指向窗口左端，right指向窗口右端。窗口不断滑动的过程其实就是left++，right++的过程，直至right移至数列末端。

01

【c++算法篇】滑动窗口

滑动窗口是一种常用的算法技术，它适用于需要检查序列（如数组或字符串）中的一系列连续元素的问题。通过维护序列中的一段特定大小的连续元素集，滑动窗口减少了不必要的重复计算，从而优化了性能。这种技术经常用于求解最大或者最小总和、长度满足特定条件的子串或子数组的问题。

00

别用 KMP 了， Rabin-Karp 算法了解下？

经常有读者留言，请我讲讲那些比较经典的算法，我觉得有这个必要，主要有以下原因： 1、经典算法之所以经典，一定是因为有独特新颖的设计思想，那当然要带大家学习一波。 2、我会尽量从最简单、最基本的算法切入，带你亲手推导出来这些经典算法的设计思想，自然流畅地写出最终解法。一方面消除大多数人对算法的恐惧，另一方面可以避免很多人对算法死记硬背的错误习惯。我之前用状态机的思路讲解了 KMP 算法，说实话 KMP 算法确实不太好理解。不过今天我来讲一讲字符串匹配的另一种经典算法：Rabin-Karp 算法，这是一个很简单优雅的算法。本文会由浅入深地讲明白这个算法的核心思路，先从最简单的字符串转数字讲起，然后研究一道力扣题目，到最后你就会发现 Rabin-Karp 算法使用的就是滑动窗口技巧，直接套前文讲的滑动窗口算法框架就出来了，根本不用死记硬背。废话不多说了，直接上干货。首先，我问你一个很基础的问题，给你输入一个字符串形式的正整数，如何把它转化成数字的形式？很简单，下面这段代码就可以做到： string s = "8264"; int number = ; for (int i = ; i < s.size(); i++) { // 将字符转化成数字 number = * number + (s[i] - '0'); print(number); } // 打印输出： // 8 // 82 // 826 // 8264 可以看到这个算法的核心思路就是不断向最低位（个位）添加数字，同时把前面的数字整体左移一位（乘以 10）。为什么是乘以 10？因为我们默认探讨的是十进制数。这和我们操作二进制数的时候是一个道理，左移一位就是把二进制数乘以 2，右移一位就是除以 2。上面这个场景是不断给数字添加最低位，那如果我想删除数字的最高位，怎么做呢？比如说我想把 8264 变成 264，应该如何运算？其实也很简单，让 8264 减去 8000 就得到 264 了。这个 8000 是怎么来的？是 8 x 10^3 算出来的。8 是最高位的数字，10 是因为我们这里是十进制数，3 是因为 8264 去掉最高位后还剩三位数。上述内容主要探讨了如何在数字的最低位添加数字以及如何删除数字的最高位，用R表示数字的进制数，用L表示数字的位数，就可以总结出如下公式： /* 在最低位添加一个数字 */ int number = ; // number 的进制 int R = ; // 想在 number 的最低位添加的数字 int appendVal = ; // 运算，在最低位添加一位 number = R * number + appendVal; // 此时 number = 82643 /* 在最高位删除一个数字 */ int number = ; // number 的进制 int R = ; // number 最高位的数字 int removeVal = ; // 此时 number 的位数 int L = ; // 运算，删除最高位数字 number = number - removeVal * R^(L-); // 此时 number = 264 如果你能理解这两个公式，那么 Rabin-Karp 算法就没有任何难度，算法就是这样，再高大上的技巧，都是在最简单最基本的原理之上构建的。不过在讲 Rabin-Karp 算法之前，我们先来看一道简单的力扣题目。高效寻找重复子序列看下力扣第 187 题「重复的 DNA 序列」，我简单描述下题目： DNA 序列由四种碱基A, G, C, T组成，现在给你输入一个只包含A, G, C, T四种字符的字符串s代表一个 DNA 序列，请你在s中找出所有重复出现的长度为 10 的子字符串。比如下面的测试用例：输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC","CCCCCAAAAA"] 解释：子串 "AAAAACCCCC" 和 "CCCCCAAAAA" 都重复出现了两次。输入：s = "AAAAAAAAAAAAA" 输出：["AAAAAAAAAA"] 函数签名如下： List<String> findRepeatedDnaSequences(String s); 这道题的拍脑袋解法比较简单粗暴，我直接穷举所有长度为 10 的子串，然后借助哈希集合寻找那些重复的子串就行了，代码如下： // 暴力解法 List<String> findRepeatedDnaSequences(String s) { int n = s.length(); // 记录出现过的子串 HashSet<String> seen = new HashSet(); // 记录那些重复出现多次的子串 // 注

02

最小覆盖子串（LeetCode 76）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

01

【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串

相信通过前两篇的文章的讲解，大家已经对滑动窗口有了较深的认识，今天我们来挑战一下！！！来做两道困难级的题目。

01

精读《算法题 - 最小覆盖子串》

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

04

常见编程模式之滑动窗口

本系列旨在介绍编程题中最常见的 16 种模式[1]。对于每一种模式会介绍其基本原理，应用场景以及经典的例题。

02

一文带你AC十道题【滑动窗口】

笔者最早接触滑动窗口是滑动窗口协议，滑动窗口协议（Sliding Window Protocol），属于 TCP 协议的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。发送方和接收方分别有一个窗口大小 w1 和 w2。窗口大小可能会根据网络流量的变化而有所不同，但是在更简单的实现中它们是固定的。窗口大小必须大于零才能进行任何操作。

01

【day03】LeetCode（力扣）每日一刷[239. 滑动窗口最大值 ][1422. 分割字符串的最大得分][1046. 最后一块石头的重量 ]

解题思路：可以使用最大堆来取出窗口中的最大值，但是问题就在于如何清空堆中不属于窗口内的数；

03

滑动窗口算法通用思想

本文详解「滑动窗口」这种高级双指针技巧的算法框架，带你秒杀几道难度较大的子字符串匹配问题：

03

【Leetcode-滑动窗口问题】

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

00

搞定大厂算法面试之leetcode精讲8.滑动窗口

搞定大厂算法面试之leetcode精讲8.滑动窗口视频教程（高效学习）:点击学习目录： 1.开篇介绍 2.时间空间复杂度 3.动态规划 4.贪心 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.单调栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其他类型题 3. 无重复字符的最长子串 (medium) 方法1.滑动窗口动画过大

05

我写了套框架，把滑动窗口算法变成了默写题

东哥带你手把手撕力扣~ 作者：labuladong 公众号：labuladong 若已授权白名单也必须保留以上来源信息我有预感本文要火，所以先罗列一下我们号的所有算法套路集锦文章：数据结构和算法学习指南动态规划框架套路详解回溯算法框架套路详解 BFS算法框架套路详解二分搜索框架套路详解双指针技巧套路汇总滑动窗口框架套路详解（本文）目前来说，以上几篇文章属于我们的镇号之宝，一直被其他人模仿，然而从未被超越。🤔 言归正传，鉴于前文我作了首诗，保你闭着眼睛也能写对二分查找的那

02

“滑动窗口”算法实例

给定一个字符串“S”，找出其中不含有重复字符的最长子串的长度。例如：S=‘ABCABCBB’，则不含重复字符的最长字串长度为3.。S=‘ABCDFG’,则不含重复字符的最长字串长度为6。要求设计一个Python程序实现该功能？

01

【数据结构和算法】子数组最大平均数 I

这道题目不难，但是确实是一道非常经典的滑动窗口问题，它可以帮助我们很好地理解滑动窗口算法的本质和应用。

01

LeetCode-3 无重复字符的最长子串

LeetCode前几道题都是经典题，今天我们学习第3题无重复字符的最长子串，这道题在秋招面试中遇见过，再次相遇，如此亲切。下面我们看看这道题的题目描述。

03

算法思想总结：滑动窗口算法

但是有一个需要注意的地方就是如果涉及到窗口求和的话。要保证数都是正整数，否则就不满足单调性。如下图这一题

01

LeetCode 03：面试关：如何找出字符串中无重复最长子串？

LeetCode第3题，“无重复字符的最长子串”，曾经面试的过程中遇到过的一道算法题。通过这道题，我们能够学到算法中一个比较常见的解题方法：滑动窗口算法。

02

面试官，你再问我滑动窗口问题试试？我有解题模板，不怕！

滑动窗口类问题是面试当中的高频题，问题本身其实并不复杂，但是实现起来细节思考非常的多，想着想着可能因为变量变化，指针移动等等问题，导致程序反复删来改去，有思路，但是程序写不出是这类问题最大的障碍。

04

BAT面试算法进阶(5)- 最长回文子串(方法一)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

02

万字长文！滑动窗口看这篇就够了！

滑动窗口协议（Sliding Window Protocol），属于TCP协议的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输，提高网络吞吐量。

02

LeetCode-76-最小覆盖字串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

05

LeetCode-76-最小覆盖字串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

01

漫画：滑动窗口系列第二讲（无重复字符的最长子串）

在上一节中，我们使用双端队列完成了滑动窗口的一道颇为困难的题目，以此展示了什么是滑动窗口。在本节中我们将继续深入分析，探索滑动窗口题型一些具有模式性的解法。

04

滴滴一面，有点。。。

这题是 LeetCode 的第 3 题，难度为中等，非常经典的滑动窗口题，但得借助哈希表来处理，有同学在滴滴面试过程中遇到过这题，只不过加了一个限制--不能使用 hashmap，大家可以思考一下加了这个限制代码应该怎么改。

01

【Day15】算法刷题（解题思路+详细注释）[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]

我们可以将三个素因子用数组保存起来，轮流将素因子与前K-1个数中的每一个数相乘，就可以得到第 k 个数；

02

BAT面试算法进阶(4)-无重复字符的最长子串

Given a string, find the length of the longest substring without repeating characters.

02

【西法带你学算法】一次搞定前缀和

我花了几天时间，从力扣中精选了五道相同思想的题目，来帮助大家解套，如果觉得文章对你有用，记得点赞分享，让我看到你的认可，有动力继续做下去。

04

☆打卡算法☆LeetCode 76、最小覆盖子串算法解析

链接：76. 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)

04

python 无重复字符的最长子串

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:

02

BAT面试算法进阶(6)- 最长回文子串(方法二)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

03

14种模式搞定面试算法编程题（PART I）

面试锦囊系列一直有收到大家的反馈，包括后台内推成功的消息、朋友的同事从创业小公司成功跳到huawei等等，非常高兴小破号的这些整理分享能够真正地帮助到大家

01

查找最大不重复子串的长度

查找最大不重复子串长度是一个常见的字符串处理问题，有多种解决思路。以下是几种常见的思路以及它们各自的时间和空间复杂度对比：

01

找到字符串中所有字母异位词（LeetCode 438）

给定两个字符串 s 和 p，找到 s 中所有 p 的「异位词」的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

01

leetcode 30. 串联所有单词的子串----滑动窗口篇八

使用两个哈希表，一个记录words数组中每个字符串出现的次数，一个记录当前滑动窗口中每一个字符串出现的次数。

03

BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法)

Given a string, find the length of the longest substring without repeating characters.

02

精读《算法 - 滑动窗口》

滑动窗口算法是较为入门题目的算法，一般是一些有规律数组问题的最优解，也就是说，如果一个数组问题可以用动态规划解，但又可以使用滑动窗口解决，那么往往滑动窗口的效率更高。

02

查找最大不重复子串的长度

查找最大不重复子串长度是一个常见的字符串处理问题，有多种解决思路。以下是几种常见的思路以及它们各自的时间和空间复杂度对比：

01

知识图谱新词挖掘1-滑动窗口解法

可以采用滑动窗口算法，这道题和力扣76题.最小覆盖字串以及力扣567题.字符串的排列很类似。 C++实现代码如下：

02

滑动窗口算法学习

给一组大小为n的整数数组，计算长度为k的子数组的最大值比如：数组{1,2,3,4,5,7,6,1,8},k=2，那么最终结果应该是7+6=13最大。最简单的是使用两层遍历，通过所有情况找出最大的一个子数组，时间复杂度O(N^2) 使用滑动窗口，从[0,k-1]的一个窗口，记录其总和，然后窗口向右移动到[1,k],再到[2,k+1]，直到数组的最尾端，找出里面总和最大的一个窗口，这样的解法就是滑动窗口算法。

01

leetcode刷题（90）——76. 最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

01

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭