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.

本来想用dp做。。。
dp[i] 存包括strs[i]的最长<Length,  Map<Character,Integer>> 但是map里边应该只存包含length结果的那些character的map 而不是所有的。

没有简化问题。。。

http://blog.csdn.net/mebiuw/article/details/52449892

“这个不是一般的DP或者暴力的解决方式，要用一下递归：

1、统计每个字母【只有小写】出现的次数 
2、找出不合法的字符【出现了，但是次数不够K】 
3、如果没有任何不合法字符，那么返回串的长度 

4、如果有不合法的字符，那么将这个串按照本轮不合法的字符位置切开（一个不合法的字符就切一刀），切开后的每一个子串递归执行1，取最长的返回”

  public int longestSubstring(String s, int k) {  
     if(s.length() < k) return 0 ;  
     HashMap<Character,Integer>count = new HashMap<>();  
     Set<Character> set = new HashSet<>();  
     for(int i = 0; i < s.length(); i++){  
       char c = s.charAt(i);  
       count.putIfAbsent(c,0);  
       count.put(c,count.get(c)+1);  
       if(count.get(c) >= k)  
         set.remove(c);  
       else   
         set.add(c);  
     }      
     if(set.size() == 0) return s.length();  
     List<String> strs = new ArrayList<>();  
     int lo = 0;    int max = 0;  
     for(int i = 0; i < s.length(); i++){  
       if(set.contains(s.charAt(i))){  
         if(lo!=i)  
           max = Math.max(max, longestSubstring(s.substring(lo,i),k));  
         lo = i+1;  
       }  
     }  
     if(lo!= s.length())   
       max = Math.max(max, longestSubstring(s.substring(lo,s.length()),k));  
     return max;  
   }