395. Longest Substring with At Least K Repeating Characters-至少有 K 个重复字符的最长子串

给你一个字符串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 <= 10^4
• s仅由小写英文字母组成
• 1 <= k <= 10^5

1.递归
Python:

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) < k:
            return 0
        length = 0
        for c in s:
            if s.count(c) < k:
                for item in s.split(c):
                    length = max(length, self.longestSubstring(item, k))
                break
        else:
            length = len(s)
        return length

Java:

class Solution {
    public int longestSubstring(String s, int k) {
        if(s.length() < k)
            return 0;
        Map<Character, Integer> map = new HashMap<>();
        Set<Character> b = new HashSet<>();
        for(Character ch: s.toCharArray())
        {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        int length = 0;
        boolean flag = false;
        for(Character ch: map.keySet())
        {
            if(b.contains(ch))
                continue;
            else
                b.add(ch);
            if(map.get(ch) < k)
            {
                flag = true;
                String[] arr = s.split(String.valueOf(ch));
                for(String t: arr)
                {
                    length = Math.max(length, longestSubstring(t, k));
                }
                return length;
            }
        }

        return s.length();
    }
}

2.双指针
Python

Java: