Java实现 LeetCode 395 至少有K个重复字符的最长子串
2023-09-14 08:58:05 时间
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 次。
class Solution {
public int longestSubstring(String s, int k)
{
int len = s.length();
if (len == 0 || k > len)
{
return 0;
}
if (k < 2)
{
return len;
}
return count(s.toCharArray(), k, 0, len - 1);
}
private static int count(char[] chars, int k, int left, int right)
{
if (right - left + 1 < k) return 0;
int[] times = new int[26]; // 26个字母
for (int i = left; i <= right; ++i)
{
times[chars[i] - 'a']++;//统计每个字母出现的次数,字符出现频次小于k,则不可能出现在结果子串中
}
//分别排除,然后挪动两个指针
while (right - left + 1 >= k && times[chars[left] - 'a'] < k)
{
++left;
}
while (right - left + 1 >= k && times[chars[right] - 'a'] < k)
{
--right;
}
if (right - left + 1 < k)//排除到剩余的字符串小于k,则直接return
{
return 0;
}
// 得到临时子串,再递归处理
for (int i = left; i <= right; ++i)
{
// 如果第i个不符合要求,切分成左右两段分别递归求得
if (times[chars[i] - 'a'] < k)
{
return Math.max(count(chars, k, left, i - 1), count(chars, k, i + 1, right));
}
}
return right - left + 1;
}
}
相关文章
- java long string 转换_Java long 转成 String的实现[通俗易懂]
- fileinputstream java_Java FileInputStream close()方法
- java输出值取后两位小数,Java输出结果保留两位小数
- java中多态_java之多态
- java启动器_JAVA基础:Java 启动器如何查找类
- Java 设计模式最佳实践:二、创建型模式
- n皇后问题 回溯法java_Java解决N皇后问题
- 【说站】java Lock提供哪些类?
- bytebuf使用_java byte类型
- Java cast_java concat方法
- Java支付宝API电脑网站支付
- Java集合面试题_java是什么
- 苹果电脑Java开发工具:IntelliJ IDEA 2023
- java计算指定日期的农历代码详解编程语言
- Java基础加强之并发(三)Thread中start()和run()的区别详解编程语言
- 中的应用Java中MySQL的灵活运用(mysql在java代码)
- Java Set.toArray()方法:用Set集合中的所有对象创建一个数组
- 数据处理在Java中处理Redis过期数据(redisjava过期)
- Using Java to Work with MongoDB: A Guide for Developers(java操作mongodb)
- Java Redis封装简介(javaredis封装)
- Linux平台上C语言接口调用Java语言实现(linux c调java)
- 如何在Linux系统中安装Java(linux中安装java)
- Java程序中使用Redis链接提升效率(redis 链接java)