1.题目基本信息

1.1.题目描述

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

如果不存在这样的子字符串，则返回 0。

1.2.题目地址

https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/

2.解题方法

2.1.解题思路

滑动窗口 / 递归

2.2.解题步骤

第一步，从小到大枚举每种字符种类数

第二步，构建维护变量。l和r分别维护滑动窗口的左右指针；win维护窗口中各个字符的频数；cnt1维护窗口字符种类的个数；cnt2维护窗口中字符频数小于k但大于0的字符种类数

第三步，进行滑窗

• 3.1.更新cnt1、cnt2和win

• 3.2.根据cnt收缩窗口，并更新相应的维护变量

• 3.3.根据维护变量更新结果变量

3.解题代码

python代码

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # 思路1：滑动窗口
        n = len(s)
        result = 0
        # 第一步，从小到大枚举每种字符种类数
        for cnt in range(1, 27):
            # 第二步，构建维护变量。l和r分别维护滑动窗口的左右指针；win维护窗口中各个字符的频数；cnt1维护窗口字符种类的个数；cnt2维护窗口中字符频数小于k但大于0的字符种类数
            l, r = 0, 0
            win = [0] * 26
            cnt1 = cnt2 = 0
            # 第三步，进行滑窗
            while r < n:
                # 3.1.更新cnt1、cnt2和win
                if win[ord(s[r]) - ord('a')] == 0:
                    cnt1 += 1
                    cnt2 += 1
                if win[ord(s[r]) - ord('a')] == k - 1:
                    cnt2 -= 1
                win[ord(s[r]) - ord('a')] += 1
                # 3.2.根据cnt收缩窗口，并更新相应的维护变量
                while cnt2 > cnt:
                    if win[ord(s[l]) - ord('a')] == 1:
                        cnt1 -= 1
                        cnt2 -= 1
                    if win[ord(s[l]) - ord('a')] == k:
                        cnt2 += 1
                    win[ord(s[l]) - ord('a')] -= 1
                    l += 1
                # 3.3.根据维护变量更新结果变量
                if cnt2 == 0:
                    result = max(result, r - l + 1)
                r += 1
        return result
    
    def longestSubstring2(self, s: str, k: int) -> int:
        # 思路2：递归
        if len(s) < k:
            return 0
        freq = Counter(s)
        for c in set(s):
            if freq[c] < k:
                return max(self.longestSubstring(s1, k) for s1 in s.split(c))
        return len(s)

c++代码

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size();
        int result = 0;
        for (int cnt = 1; cnt <= 26; cnt++) {
            vector<int> win(26, 0);
            int l = 0, r = 0;
            int cnt1 = 0, cnt2 = 0;
            while (r < n) {
                if (win[s[r] - 'a'] == 0) {
                    cnt1++; cnt2++;
                }
                if (win[s[r] - 'a'] == k - 1) {
                    cnt2--;
                }
                win[s[r] - 'a']++;
                while (cnt1 > cnt) {
                    if (win[s[l] - 'a'] == 1) {
                        cnt1--; cnt2--;
                    }
                    if (win[s[l] - 'a'] == k) {
                        cnt2++;
                    }
                    win[s[l] - 'a']--;
                    l++;
                }
                if (cnt2 == 0) {
                    result = max(result, r - l + 1);
                }
                r++;
            }
        }
        return result;
    }
};

4.执行结果