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 = 3Output:3The longest substring is "aaa", as 'a' is repeated 3

Example 2:

Input:s = "ababbc", k = 2Output:5The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3

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

class Solution { public int longestSubstring(String s, int k) { if(s == null || k < 0) return 0; HashMap hashmap = new HashMap(); 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。