【python-leetcode340-滑动窗⼝法】⾄多包含K个不同字符的最
长⼦串
问题描述：给定⼀个字符串s，到⾄多包含k个不同字符得最长⼦串的长度。
⽐如s="cebea"，k=2，那么输出结果就是3，因为此时"ebe"满⾜条件：⾄多包含两个不同字符，且⼦串最长
⽐如s="world"，k=4，那么输出结果就是4，因为"worl"和"orld"满⾜条件：⾄多包含4个不同字符，且⼦串最长
class Solution:
def lengthOfLongestSubstringKDistinct(self, s, k):
tmp = 0 #⽤于记录满⾜条件得最⼤值
for i in range(1,len(s)+1):#步长从1到len(s)+1
for j in range(len(s)-i+1):#窗⼝左端
print(s[j:j+i])
if len(set(s[j:j+i])) == k:#如果窗⼝中取集合后的不同字符就是k个
tmp = max(tmp,i)#更新tmp的值
print("tmp:{}".format(tmp))
return tmp #最后返回即可
过程：
c
e
b
e
a
ce
tmp:2
字符串长度 pythoneb
tmp:2
be
tmp:2
ea
tmp:2
ceb
ebe
tmp:3
bea
cebe
ebea
cebea
第⼆种⽅法：
思路: ⼀个hash表和⼀个左边界标记. 遍历字符串将其加⼊到hash表中, 不同字符多于k个了, 就从左边开始删字符. 直到hash表不同字符长度等于k.此时字符串的长度就是当前字符和左边界的距离。
class Solution:
def lengthOfLongestSubstringKDistinct(self,s,k):
from collections import defaultdict
#使⽤python中的collections.defaultdict
#字典中存储的整型的值默认为0
hash = defaultdict(int)
max_num = 0 #⽤于存放最⼤值
start = 0 #滑动窗⼝的左端
#从字符串左开始遍历
for i in range(len(s)):
#遍历到⼀个字符，使得字典中对应得字符加1
hash[s[i]] += 1
while len(hash)>k:
hash[s[start]] -= 1
if hash[s[start]] == 0:
del hash[s[start]]
start += 1
max_num = max(max_num,i-start+1)
return max_num
由于leetcode没会员，不能解锁，不能保证能过。但思路应该没问题。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。