Longest Substring with At Least K Repeating Characters，longestrepeating

Longest Substring with At Least K Repeating Characters，longestrepeating

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.

思路：刚开始想用滑动窗口法，但是失败，看了这个链接，才弄懂是怎么个算法；https://all4win78.wordpress.com/2016/09/08/leetcode-395-longest-substring-with-at-least-k-repeating-characters/comment-page-1/  总体思想就是divide and conquer.

算法基本原理是，先遍历整个string，并记录每个不同的character的出现次数。如果所有character出现次数都不小于k，那么说明整个string就是满足条件的longest substring，返回原string的长度即可；如果有character的出现次数小于k，假设这个character是c，因为满足条件的substring永远不会包含c，所以满足条件的substring一定是在以c为分割参考下的某个substring中。所以我们需要做的就是把c当做是split的参考，在得到的String[]中再次调用我们的method，找到最大的返回值即可。

public class Solution {
    public int longestSubstring(String s, int k) {
        if(s == null || k<0) return 0;
        HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(hashmap.containsKey(c)){
                hashmap.put(c, hashmap.get(c)+1);
            } else {
                hashmap.put(c, 1);
            }
        }
        
        Character delimiter = null;
        for(Character c: hashmap.keySet()){
            if(hashmap.get(c)<k){
                delimiter = c;
            }
        }
        
        if(delimiter == null) {
            return s.length();
        }
        int maxlen = 0;
        String[] splits = s.split(""+delimiter);
        for(String str: splits){
            maxlen = Math.max(maxlen, longestSubstring(str,k));
        }
        return maxlen;
    }
}