原文链接: https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters
英文原文
Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.
Example 1:
Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input: s = "ababbc", k = 2 Output: 5 Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Constraints:
1 <= s.length <= 104sconsists of only lowercase English letters.1 <= k <= 105
中文题目
给你一个字符串 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 <= 104s仅由小写英文字母组成1 <= k <= 105
通过代码
高赞题解
各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 34 天。今天力扣上的每日一题是「395. 至少有K个重复字符的最长子串」。
解题思路
本题要求的一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 $k$。
求最长子字符串/区间的这类题一般可以用滑动窗口来做，但是本题滑动窗口的代码不好写，我改用递归。也借本题来帮助大家理解递归。
- 重点：我们在调用递归函数的时候，把递归函数当做普通函数（黑箱）来调用，即明白该函数的输入输出是什么，而不用管此函数内部在做什么。
下面是详细讲解。
- 递归最基本的是记住递归函数的含义（务必牢记函数定义）：本题的
longestSubstring(s, k)函数表示的就是题意，即求一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 $k$。函数入参 $s$ 是表示源字符串；$k$ 是限制条件，即子字符串中每个字符最少出现的次数；函数返回结果是满足题意的最长子字符串长度。
- 递归的终止条件（能直接写出的最简单 case）：如果字符串 $s$ 的长度少于 $k$，那么一定不存在满足题意的子字符串，返回 0；
- 调用递归（重点）：如果一个字符 $c$ 在 $s$ 中出现的次数少于 $k$ 次，那么 $s$ 中所有的包含 $c$ 的子字符串都不能满足题意。所以，应该在 $s$ 的所有不包含 $c$ 的子字符串中继续寻找结果：把 $s$ 按照 $c$ 分割（分割后每个子串都不包含 $c$），得到很多子字符串 $t$；下一步要求 $t$ 作为源字符串的时候，它的最长的满足题意的子字符串长度（到现在为止，我们把大问题分割为了小问题($s$ → $t$)）。此时我们发现，恰好已经定义了函数
longestSubstring(s, k)就是来解决这个问题的！所以直接把longestSubstring(s, k)函数拿来用，于是形成了递归。
- 未进入递归时的返回结果：如果 $s$ 中的每个字符出现的次数都大于 $k$ 次，那么 $s$ 就是我们要求的字符串，直接返回该字符串的长度。
总之，通过上面的分析，我们看出了：我们不是为了递归而递归。而是因为我们把大问题拆解成了小问题，恰好有函数可以解决小问题，所以直接用这个函数。由于这个函数正好是本身，所以我们把此现象叫做递归。小问题是原因，递归是结果。而递归函数到底怎么一层层展开与终止的，不要用大脑去想，这是计算机干的事。我们只用把递归函数当做一个能解决问题的黑箱就够了，把更多的注意力放在拆解子问题、递归终止条件、递归函数的正确性上来。
希望我说的这些能对你理解递归有所帮助。
代码
三种语言的代码如下，Python 是行数最少的。
[]class Solution(object): def longestSubstring(self, s, k): if len(s) < k: return 0 for c in set(s): if s.count(c) < k: return max(self.longestSubstring(t, k) for t in s.split(c)) return len(s)
[]class Solution { public: int longestSubstring(string s, int k) { if (s.size() < k) return 0; unordered_set<char> chars(s.begin(), s.end()); unordered_map<char, int> counter; for (char c : s) counter[c] ++; for (char c : chars) { vector<string> t; if (counter[c] < k) { split(s, t, c); int res = 0; for (string tn : t) { res = max(res, longestSubstring(tn, k)); } return res; } } return s.size(); } void split(const string& s, vector<string>& sv,const char flag = ' ') { sv.clear(); istringstream iss(s); string temp; while (getline(iss, temp, flag)) { sv.push_back(temp); } } };
[]class Solution { public int longestSubstring(String s, int k) { if (s.length() < k) return 0; 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; } } return s.length(); } }
- 时间复杂度：$O(N * 26 * 26)$，因为函数最多执行 26 次，
for循环遍历一次是26个字符，循环里面对 $s$ 分割时间复杂度是$O(N)$。超过了 84.40% 的提交。 - 空间复杂度：$O(26 * 26)$，函数执行 26 次，每次开辟 26 个字符的set空间。
刷题心得
很多同学都被递归绕进去了，其实把递归函数当做普通函数就好了。
OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。
祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 54351 | 104525 | 52.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
