给定一个长度为 n 的字符串 s ,找出最多包含 k 种不同字符的最长连续子串的长度。
数据范围: , 字符串中仅包含小写英文字母
# -*- coding: utf-8 -*- import collections # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @param k int整型 # @return int整型 # class Solution1: """ 题目: https://www.nowcoder.com/practice/04c926ef687340c3842a72edb5c23ede?tpId=196&tqId=40446&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 算法1: 双指针i, j,分别指向窗口的左右边界,是用哈希表count统计窗口内每个字符出现次数,当前窗口不同字符的数量diffCnt就是count的长度。 当diffCnt小于等于k时,移动右边界,更新res;否则移动左边界。重复该步骤,直到遍历完字符串s。 复杂度: 时间复杂度:O(n) 空间复杂度:O(k) """ def longestSubstring(self, s, k): # write code here n = len(s) count = {} i, j, res = 0, 0, 0 while j < n: diffCnt = len(count) if diffCnt <= k: if s[j] not in count: count[s[j]] = 1 res = max(res, j - i) # k = 3, s = "abcdef", i = 0, j = 3,计算长度diffCnt为j - i else: count[s[ j]] += 1 # # k = 3, s = "abccdef", i = 0, j = 3,计算长度diffCnt为j - i + 1 res = max(res, j - i + 1) j += 1 else: count[s[i]] -= 1 if count[s[i]] == 0: count.pop(s[i]) i += 1 return res class Solution: """ 参考: 大神:fred-coder 算法2: 遍历字符串s: 使用哈希表count统计每个字符串出现次数,不同字符的个数就是count的长度,start记录当前有效区间的左边界,右边界为i。 当count的长度小于等于k时,我们更新res;否则,我们移动左边界start,使得[start, i]区间内的不同字符数量满足小于等于k 复杂度: 时间复杂度:O(n) 空间复杂度:O(k) """ def longestSubstring(self, s, k): # write code here count = collections.defaultdict(int) start, res = 0, 0 for i, ch in enumerate(s): count[ch] += 1 if len(count) <= k: res = max(res, i - start + 1) else: j = start while j < i - k + 1 and len(count) > k: count[s[j]] -= 1 if count[s[j]] == 0: count.pop(s[j]) j += 1 start = j return res if __name__ == "__main__": sol = Solution() # s, k = "abcck", 1 # s, k = "abcck", 2 s, k = "efsarcbynec", 5 # s, k = "jmowfrxsjybl", 1 res = sol.longestSubstring(s, k) print res