[刷题]Leetcode 395. 至少有K个重复字符的最长子串
文章目录
同学去面抖音被问到了这道题,赶紧去看了一下 发现自己也不会
哈哈哈哈哈,so.. 记个笔记 便于复习
题目描述
找到给定字符串(由小写字符组成)中的最长子串 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,找出最长的这样的子串
还有题目没有说太明确,其实由小写字符组成就是说只有‘a-z‘的小写字母,这样我们就可以方便地用数组来统计啦~
思路:
如果不满足条件的字符出现在了字符串两边好说,我们只需要把两边不满足条件的字符去掉
麻烦的是 字符可能出现在中间 于是考虑用分治法去解决这个问题 把大问题划分为几个小问题, 如果字符出现在了中间 我们就把字符串从这个字符这里劈开,左边去求解这个问题,右边也去求解这个问题,最后取左右俩边结果的最大值就OK了
关于某个字符是否满足条件,我们只需要提前遍历一遍字符串,统计一下就OK了~
代码如下:
class Solution {
public int longestSubstring(String s, int k) {
if(s==null) return 0;
if(s.length()==0) return 0;
if(k<=1) return s.length();
return count(s, k, 0, s.length()-1);
}
public int count(String s, int k, int left , int right){
if(right-left+1<k) return 0;
int[] cnt = new int[26];
for(int i=left;i<=right;i++){
++cnt[s.charAt(i)-'a'];
}
// 去除左右两边不满足条件的字符
while(right-left+1>=k && cnt[s.charAt(left)-'a']<k){
left++;
}
while(right-left+1>=k && cnt[s.charAt(right)-'a']<k){
right--;
}
if(right-left+1<k) return 0;
// 劈开分治
for(int i =left;i<=right;i++){
// 只需要劈开一次就可以返回了,
// 因为即使右边还有不满足条件的字符,
// 也会在其子阶段求解得到了
if(cnt[s.charAt(i)-'a']<k){
return Math.max(count(s, k, left, i-1), count(s, k, i+1, right));
}
}
return right-left+1;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论