395. 至少有 K 个重复字符的最长子串

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
Star
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
示例 1：
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2：
输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
提示：
  • 1 <= s.length <= 104
  • s 仅由小写英文字母组成
  • 1 <= k <= 105

滑动窗口

思路
通过一层循环限定窗口内的字符种类数量
题解
class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        ans = 0
        total_kind = len(set(s))
        for kind_limit in range(1, total_kind+1): # 窗口内字符种类的上限，用来限定窗口的长度
            valid = 0 # 满足「出现次数不少于 k」条件的，窗口内字符种类
            
            right, left = 0, 0
            window = collections.defaultdict(int)
            while right < len(s):
                window[s[right]] += 1
                if window[s[right]] == k:
                    valid += 1
                right += 1

                # 当窗口内字符种类数超过限制时，左边界收缩
                while len(window) > kind_limit:
                    if window[s[left]] == k:
                        valid -= 1
                    window[s[left]] -= 1
                    if window[s[left]] == 0:
                        del window[s[left]]
                    
                    left += 1
                
                # 窗口内字符种类 等于 满足条件的字符种类时，取此时的窗口长度
                if len(window) == valid:
                    ans = max(ans, right - left)
                
        
        return ans