LeetCode 1100. 长度为 K 的无重复字符子串（滑动窗口）

文章目录

1. 题目2. 解题

1. 题目

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的 数目。

示例 1： 输入：S = "havefunonleetcode", K = 5 输出：6 解释： 这里有 6 个满足题意的子串，分别是： 'havef','avefu','vefun','efuno','etcod','tcode'。 示例 2： 输入：S = "home", K = 5 输出：0 解释： 注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。 提示： 1 <= S.length <= 10^4 S 中的所有字符均为小写英文字母 1 <= K <= 10^4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-k-length-substrings-with-no-repeated-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

set 查重 class Solution {//C++ public: int numKLenSubstrNoRepeats(string S, int K) { int i = 0, j = 0, n = S.size(),count = 0; unordered_set<char> set; for( ; j < n; ++j) { while(set.size() >= K || set.count(S[j])) set.erase(S[i++]);//长度大了，或者包含j字符 set.insert(S[j]);//j无重复了 if(set.size()==K)//包含j字符结尾的字符串有1个 count++; } return count; } };

32 ms 8.8 MB

class Solution:#py3 def numKLenSubstrNoRepeats(self, S: str, K: int) -> int: i, j = 0, 0 count = 0 st = set() while j < len(S): while len(st) >= K or S[j] in st: st.remove(S[i]) i += 1 st.add(S[j]) if len(st)==K: count += 1 j += 1 return count

64 ms 13.7 MB

---

我的博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！