Sliding Window - 395. Longest Substring with At Least K Repeating Characters

395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

思路：

题目意思是给定一个字符串和一个k值，要求找出一个最长子串，子串中的字母至少出现k次。可以考虑找出字符串中出现次数小于k次的字符，然后以这种字符为界限，截取字符串，来递归找出最长子串。

代码：

java：

class Solution {

    public int longestSubstring(String s, int k) {

        if (s == null || s.length() == 0) return 0;
    
        int[] hash = new int[26];
        for(char c : s.toCharArray()) hash[c - 'a']++;

        // 只要有一个字符少于k次出现，那就不符合要求
        boolean fullString = true;
        for (int i = 0; i < s.length(); i++) {
            if (hash[s.charAt(i) - 'a'] > 0 && hash[s.charAt(i) - 'a'] < k) {
                fullString = false;
            }
        }

        if (fullString == true) return s.length();
        
        // 递归找出最长子串
        int begin = 0, end = 0, res = 0;
        while (end < s.length()) {
            if (hash[s.charAt(end) - 'a'] < k) {
                res = Math.max(res, longestSubstring(s.substring(begin, end), k));
                begin = end + 1;
            }
            end++;
        }

        // 最后考虑begin和end之间如果还有字符（end到字符串最后，begin还没有到）就继续找
        res =  Math.max(res, longestSubstring(s.substring(begin, end), k));
        return res;
    }
}