leetcode 395 至少有K个重复字符的最长子串
2024-09-30 04:17:44
找到给定字符串（由小写字符组成）中的最长子串 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： 暴力枚举
class Solution {
public int longestSubstring(String s, int k) {
if(s.length() <= 0){
return 0;
}
int size = 0;
char[] array = s.toCharArray();
for(int i=0; i<array.length;i++){
int[] count = new int[26];
count[array[i] - 'a'] ++;
for(int j=i; j< array.length;j++){
if(i!=j) {
count[array[j] - 'a']++;
}
if( Judge(count, k ) && (j-i+1)>size){
size = j-i+1;
}
}
}
return size;
}
boolean Judge(int[] count ,int k ){
for(int i=0; i<count.length;i++){
if( count[i] > 0 && count[i] <k ){
return false;
}
}
return true;
}
}
思路2：
规律：如果一个字符串中有一个字符出现的次数少于k，那么这个字符必定不在结果中。
利用这个出现次数少于k的字符来切分字符数组，对于左边和右边进行递归操作
public int longestSubstring(String s, int k) {
return longestSubstringSub(s, k, 0, s.length() - 1);
}
private int longestSubstringSub(String s, int k, int start, int end) {
if(end<=start){
return 0;
}
int[] count =new int[26];
for(int i=start; i<=end; i++){
count[s.charAt(i) -'a']++;
}
// for(int i=start; i<=end;i++){
// if(count[s.charAt(i) - 'a'] > 0 && count[s.charAt(i) - 'a'] <k){
// return Math.max( longestSubstringSub(s, k,start,i-1), longestSubstringSub(s,k,i+1, end));
// }
// }
int res = end - start + 1;
// return res;
for(int i = 0; i < 26; i++){
if(count[i] > 0 && count[i] < k){
int pos = s.indexOf((char)(i + 'a'), start);
res = Math.max(longestSubstringSub(s, k, start, pos - 1), longestSubstringSub(s, k, pos + 1, end));
}
}
return res;
}
最新文章
- oracle的decode函数在mysql的实现
- springmvc和struts2的差别
- 我的Android第三章：Android的组件介绍
- Redis学习笔记（一）
- 纸上谈兵：表（list）
- HTML、XHTML XML和DHTML的区别
- Android Studio开发第四篇版本管理Git（下）
- ArrayList等常见集合的排序问题
- Java集合类: Set、List、Map、Queue使用场景梳理
- MongoDB - MongoDB CRUD Operations, Query Documents, Project Fields to Return from Query
- Think PHP 提示验证码输入错误
- Java系统程序员修炼之道
- switch语法中break,default作用说明
- Mysql大小写敏感的问题 --转
- activiti总结
- cocos2dx --- button点击放大中心
- String类之substring--->查找某位置对应的字
- Superwebsocket 模拟微信聊天室
- Spring 框架系列之事务管理
- POJ 2417 Discrete Logging BSGS