【python-leetcode340-滑动窗口法】至多包含 K 个不同字符的最长

发布时间：2020-12-20 09:55:12 所属栏目：Python 来源：网络整理

导读：问题描述：给定一个字符串s，找到至多包含k个不同字符得最长子串的长度。比如s="cebea"，k=2，那么输出结果就是3，因为此时"ebe"满足条件：至多包含两个不同字符，且子串最长比如s="world"，k=4，那么输出结果就是4，因为"worl"和"orld"满足条件：至多包含

问题描述：给定一个字符串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
eb
tmp:2
be
tmp:2
ea
tmp:2
ceb
ebe
tmp:3
bea
cebe
ebea
cebea

第二种方法：

思路:?一个hash表和一个左边界标记.?遍历字符串将其加入到hash表中,?不同字符多于k个了,?就从左边开始删字符.?直到hash表不同字符长度等于k.此时字符串的长度就是当前字符和左边界的距离。

from collections import defaultdict
        使用python中的collections.defaultdict
        字典中存储的整型的值默认为0
        hash = defaultdict(int)
        max_num = 0 用于存放最大值
        start = 0 滑动窗口的左端
        从字符串左开始遍历
        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没会员，不能解锁，不能保证能过。但思路应该没问题。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!