leetcode 395 Longest Substring with At Least K Repeating Characters

lc395 Longest Substring with At Least K Repeating Characters

思路是按子串中不同字母的个数来计算，1~26

每次计算n个不同字母所能构成的最长子串

记录其中最长子串

单次循环中，用双指针end向后遍历s，begin用来计算子串长度

当见过的字母个数 == n且这些字母出现次数都大于等于k

说明begin~end这个子串符合条件，更新maxLen

若 >，则需要向后移动begin，使其变为==

若<，不需要操作

 1 class Solution {
 2     public int longestSubstring(String s, int k) {
 3         if(s.length() == 0 ||s.length() < k)
 4             return 0;
 5         int max = 0;
 6         for(int i=1; i<=26; i++){
 7             max = Math.max(max, helper(s, k, i));
 8         }
 9         
10         return max;
11     }
12     
13     private int helper(String s, int k, int abcNum){
14         int[] count = new int[128];
15         int begin = 0, end = 0;
16         int seenChar = 0, noLessThanK = 0;
17         int res = 0;
18         
19         while(end < s.length()){
20             if(count[s.charAt(end)]++ == 0)
21                 seenChar++;
22             if(count[s.charAt(end++)] == k)
23                 noLessThanK++;
24             
25             /*while(seenChar > abcNum){
26                 if(count[s.charAt(begin)]-- == k)
27                     noLessThanK--;
28                 if(count[s.charAt(begin++)] == 0)
29                     seenChar--;
30             }*/
31             while(seenChar > abcNum){
32                 if(count[s.charAt(begin)]-- == 1)
33                     seenChar--;
34                 if(count[s.charAt(begin++)] == k-1)
35                     noLessThanK--;
36             }
37             
38             if(seenChar == noLessThanK && seenChar == abcNum)
39                 res = Math.max(res, end-begin);
40         }
41         
42         return res;
43     }
44 }

法二：

分治法

统计字符出现次数，用哪些次数少于k的字符将字符串隔开，因为任何包含这些字符的子串肯定不满足条件，这些子串就是子问题

 1 class Solution {
 2     public int longestSubstring(String s, int k) {
 3         if(s.length() == 0 || k == 0)
 4             return 0;
 5         
 6         int[] count = new int[128];
 7         int res = 0;
 8         
 9         for(char c : s.toCharArray())
10             count[c]++;
11         
12         List<Integer> split = new ArrayList<Integer>();
13         
14         for(int i=0; i<s.length(); i++){
15             if(count[s.charAt(i)] < k)
16                 split.add(i);
17         }
18         
19         if(split.size() == 0)
20             return s.length();
21         split.add(0, -1);
22         split.add(s.length());
23         
24         for(int i=1; i<split.size(); i++){
25             int start = split.get(i-1) + 1;
26             int end = split.get(i);
27             int max = longestSubstring(s.substring(start, end), k);
28             res = Math.max(res, max);
29         }
30         return res;
31     }
32 }