Leetcode刷题java之395. 至少有K个重复字符的最长子串（一天一道编程题之三十二天）

短命女 2023-07-18 04:47 15阅读 0赞

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了78.25% 的用户

内存消耗 :37.7 MB, 在所有 Java 提交中击败了8.10%的用户

题目：

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:

输入:  
s = "aaabb", k = 3

输出:  
3

最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2:

输入:  
s = "ababbc", k = 2

输出:  
5

最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

递归拆分+分治

代码：

class Solution {
        public int longestSubstring(String s, int k) {
            if(k<=1)
            {
                return s.length();
            }
            if(k>s.length())
            {
                return 0;
            }
            char[] ch=s.toCharArray();
            return help(ch,k,0,s.length()-1);
    
        }
        public int help(char[] ch,int k,int left,int right)
        {
            if(right-left+1<k)
            {
                return 0;
            }
            int[] times=new int[26];
            for(int i=left;i<=right;i++)
            {
                times[ch[i]-'a']++;
            }
            while(right - left + 1 >= k&&times[ch[left]-'a']<k)
            {
                left++;
            }
            while(right - left + 1 >= k&&times[ch[right]-'a']<k)
            {
                right--;
            }
            if(right-left+1<k)
            {
                return 0;
            }
            for(int i=left;i<=right;i++)
            {
                if(times[ch[i]-'a']<k)
                {
                    return Math.max(help(ch,k,left,i-1),help(ch,k,i+1,right));
                }
            }
            return right-left+1;
        }
    }