Leetcode:395. 至少有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 次。

思路

思路1

计算字符串中每个字符出现次数，然后是用双指针去除前后不满足的字符。中间字符串遍历，如有少于k次地则切割分治分别计算，并取最大值

代码

代码1

class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0 || k > s.length()){
            return 0;
        }
        if (k < 2){
            return s.length();
        }
        
        return subStringHelper(s, 0, s.length() - 1, k);
    }
    
    
    private int subStringHelper(String s, int start, int end, int k){
        if (end - start + 1 < k){
            return 0;
        }
        
        int[] chNum = new int[26];
        for(int i = start; i <= end; i++){
            chNum[s.charAt(i) - 'a'] += 1;
        }
        while(end - start + 1 >= k && chNum[s.charAt(start) - 'a'] < k){
            start++;
        }
        while(end - start + 1 >= k && chNum[s.charAt(end) - 'a'] < k){
            end--;
        }
        
        if (end - start + 1 < k){
            return 0;
        }
        for(int i = start; i <= end; i++){
            if (chNum[s.charAt(i) - 'a'] < k){
                return Math.max(subStringHelper(s, start, i - 1, k), subStringHelper(s, i + 1, end, k));
            }
        }
        return end - start + 1;
    }
}