Leecode每日一题-至少有 K 个重复字符的最长子串_J___code的博客-程序员秘密

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：
输入：s = “aaabb”, k = 3
输出：3
解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。

示例 2：
输入：s = “ababbc”, k = 2
输出：5
解释：最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。

提示：
1 <= s.length <= 104
s 仅由小写英文字母组成
1 <= k <= 105

假设s=“aaeabceccbdded”,k=3。可以看出b出现的次数小于k，所以最长子串肯定不包括b。以b为分割点可以分出"aaea",“cecc”,“dded”，即最长子串只能在这三个子串中进行判断。再在这三个子串中以次数小于k的字母为分割点（比如aaea中就是e）进行分割操作。如果字符串中每一个字母出现次数都不少于k，那么这个字符串本身肯定就是最长子串了。

public int longestSubstring(String s, int k) {
    
        //递归终止条件
        if(s.length() < k){
    
            return 0;
        }
        //counter用来记录字符串s中每一个字母出现次数
        HashMap<Character, Integer> counter = new HashMap();
        for(int i=0;i<s.length();i++){
    
            counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);
        }

        for (char c : counter.keySet()) {
    
            if (counter.get(c) < k) {
    
                int res = 0;
                for (String t : s.split(String.valueOf(c))) {
    
                    res = Math.max(res, longestSubstring(t, k));
                }
                return res;
            }
        }
        //当s中所有字母出现的次数都大于k的时候，则最大子串就是s本身
        return s.length();
}

参考Leecode题解@负雪明烛

本文链接：https://blog.csdn.net/qq_41398418/article/details/114190499

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

带参数的信号_melon_eater的博客-程序员秘密

转自：http://blog.csdn.net/q1007729991/article/details/53893743前面不管我们是使用 signal 信号注册函数还是 sigaction 信号注册函数，我们都只注册了带一个参数的信号处理函数 void handler(int sig)。实际上，我们也可以使用带参数的的信号处理函数。signal 函数没办法注册一个带附加参数的信号处理函数，但是 ...

iOS UITableView(二)原生代码实现_意外i的博客-程序员秘密

1.创建UITableView 首先在viewController类的扩展里，添加两个协议，分别是UITableViewDataSource和UITableViewDelegate1.1创建一个UITableView，并添加到根View 初始化一个UITableView对象设置当前类为tableView的委托对象以及数据源最后添加到self.view根视图上1.2设...

MySQL - 存储过程，函数，触发器_不回头~的博客-程序员秘密

存储过程简介SQL语句需要先编译然后执行，而存储过程（Stored Procedure）是一组为了完成特定功能的SQL语句集，经编译后存储在数据库中，用户通过指定存储过程的名字并给定参数（如果该存储过程带有参数）来调用执行它。存储过程是可编程的函数，在数据库中创建并保存，可以由SQL语句和控制结构组成。当想要在不同的应用程序或平台上执行相同的函数，或者封装特定功能时，存储过程是非常有用的。数据库中的存储过程可以看做是对编程中面向对象方法的模拟，它允许控制数据的访问方式。存储过程的优点：(1).增强S

使用Idea创建ssm项目，SpringMVC+Spring+MyBatis+Maven整合_idea 如何创建ssm项目_七夜琉璃的博客-程序员秘密

一.简介SSM（Spring+SpringMVC+MyBatis）框架集由Spring、SpringMVC、MyBatis三个开源框架整合而成，常作为数据源较简单的web项目的框架。其中Spring是一个轻量级的控制反转（IoC）和面向切面（AOP）的容器框架。 SpringMVC分离了控制器、模型对象、分派器以及处理程序对象的角色，这种分离让它们更容易进行定制。 MyBatis是...

周记录（第三周）_种植菜苗第三周记录_weixin_44365784的博客-程序员秘密

周记（第三周）1.文件操作1．打开文件 open()参数1：文件路径路径 url 统一资源定位符相对路径：就像给别人指路一样： e.g.在某某大厦的对面。针对文件的相对路径的表示，从当前目录开始计算 1.txt ==> 具体文件前没有任何表示时，默认为当前目录和 ./1.txt 是一个位置 ./1.txt ==> ./ 代表当前目录中的1.txt

【笔记】verilog 学习笔记(一)_tfand的博客-程序员秘密

1、版本+编译时间2、提供取反和不取反用于测试寄存器3、提供Debug LED和Test point4、计数器清零及为什么清零5、锁相环状态查询、失效历史查询6、握手信号寄存器可查询7、通信接口应该有时能、清零、镜像RAM等功能8、LocalBus提供中断、环回，流量控制等功能9、每个模块都有状态调试寄存器10、模块入口处和出口处都需要统计11、高速信号应该