给定一个长度为 n 的字符串 s ,找出最多包含 k 种不同字符的最长连续子串的长度。
数据范围: , 字符串中仅包含小写英文字母
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @param k int整型 # @return int整型 # # 问题一:如何判断子串包含多少种不同字符 # hash,hash对应value不为0的key的个数 # k为限定条件,即不能使对应的value不为9的key的个数超过k,若超过,则移动左界 class Solution: def longestSubstring(self , s: str, k: int) -> int: # write code here if len(s) <= 1: return len(s) # 定义空字典 dict_ = {} # 初始化左右界 left = right = 0 res = 0 key_count = 0 # 进入循环 while right < len(s): # 将当前right的字符加入或者更新其在dict_中的value # 需要判断当前字符是否在字典之中 if s[right] not in dict_: # 初始化key key_count += 1 dict_[s[right]] = 1 else: if dict_[s[right]] == 0: key_count += 1 # 更新对应key的value dict_[s[right]] += 1 # 如果value >= 1的key的个数超过了k,则需要移动左界并更新字典,直到满足条件 if key_count > k: while True: # 把左界上面的字符的value清为0,就维持了条件 # 具体操作:更新value,移动左界 dict_[s[left]] -= 1 # 如果-1之后,左界指向的字符在字典里面value等于0了,移动左界并且跳出循环 if dict_[s[left]] == 0: left += 1 break # 不满足上面的条件,移动左界,进行循环 left += 1 # 清零之后,更新一下key_count key_count -= 1 # 经过上面的判断,此时必然满足条件,则计算子串长度,并与上一个res比较,如果更大,则更新res temp_res = right - left + 1 if temp_res > res: res = temp_res # 在最后,移动右界 right += 1 return res
# python3 class Solution: def longestSubstring(self, s: str, k: int) -> int: # write code here lastPos = {} l, res = 0, 0 for r in range(len(s)): if s[r] in lastPos: lastPos[s[r]] = r else: if len(lastPos) < k: lastPos[s[r]] = r else: lastPos[s[r]] = r while l < lastPos[s[l]]: l += 1 lastPos.pop(s[l], None) l += 1 res = max(res, r - l + 1) return res