Leetcode 395.至少有k個重複字元的最長子串

至少有k個重複字元的最長子串

找到給定字元串（由小寫字元組成）中的最長子串 T ， 要求 T 中的每一字元出現次數都不少于 k 。輸出 T 的長度。

示例 1:

輸入:

s = "aaabb", k = 3

輸出:

3

最長子串為 "aaa" ，其中 'a' 重複了 3 次。

示例 2:

s = "ababbc", k = 2

5

最長子串為 "ababb" ，其中 'a' 重複了 2 次， 'b' 重複了 3 次。

要求是找出最長的子串，子串中的每一個字元都要重複至少k次。

思路是分治法。

1 import java.util.Stack;
 2 
 3 public class Solution{
 4     public int longestSubstring(String s, int k) {
 5         return longestSubstringSub(s, k, 0, s.length() - 1);
 6     }
 7 
 8     private int longestSubstringSub(String s, int k, int start, int end){
 9         if(start > end) return 0;
10         int[] count = new int[26];
11         for(int i = start; i <= end; i++){
12             count[s.charAt(i) - 'a']++;
13         }
14         for(int i = 0; i < 26; i++){
15             if(count[i] > 0 && count[i] < k){
16                 int pos = s.indexOf((char)(i + 'a'), start);
17                 return Math.max(longestSubstringSub(s, k, start, pos - 1), longestSubstringSub(s, k, pos + 1, end));
18             }
19         }
20         return end - start + 1;
21     }
22 }