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.

-------------------------
递归，找出当前String里数量小于k的字符的index，以这些index作为分界点，对substring进行相同操作。

O(n), n是String的长度。因为最多只有26个字符，每一层递归都会去除一个字符

class Solution {
    public int longestSubstring(String s, int k) {
        Map<Character, Integer> map = getMap(s);
        Stack<Integer> st = new Stack<>();
        st.push(-1);
        
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) < k) {
                st.push(i);
            }
        }
        
        if (st.size() == 1) return s.length();
        
        int len = 0;
        int end = s.length();
        
        while (!st.isEmpty()) {
            int start = st.pop();
            len = Math.max(len, longestSubstring(s.substring(start + 1, end), k));
            end = start;
        }
        
        return len;
    }
    
    private Map<Character, Integer> getMap(String s) {
        Map<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);  
        }
        
        return map;
    }
}