0395. Longest Substring with At Least K Repeating Characters
============================================================
题目信息
--------
:题号: 0395
:难度: Medium
:主题: 连续子串、局部字符频次、最少出现次数、最大长度
:原题: `LeetCode 0395 `_
:重点: 统计范围只限所选子串、子串中的每一种字符都必须至少出现 k 次、无合法非空子串返回 0
题目重述
--------
给定只包含小写英文字母的字符串 ``s`` 和整数 ``k``,寻找一个最长连续子串,使该子串中出现过的每一种字符,在该子串内部都至少出现 ``k`` 次。返回这个最长长度。
``s`` 的长度位于 ``[1, 10^4]``,``k`` 位于 ``[1, 10^5]``。字符在原字符串其他位置的出现次数不计入所选子串的频次;若没有任何非空子串满足要求,返回 ``0``。存在多个同样长的子串时仍只返回长度。
自建示例
--------
尾部低频字符不能加入:
.. code-block:: text
输入:s = "aaabbbc",k = 3
输出:6
解释:子串 "aaabbb" 中 a 和 b 都出现三次;加入末尾 c 后,c 只出现一次,不再合法。
没有字符达到要求:
.. code-block:: text
输入:s = "abc",k = 2
输出:0
解释:任意非空子串中的每个字符最多出现一次,无法满足至少两次。
低频字符一定是合法子串的分界
------------------------------
对当前区间统计 26 个字符频次。若某字符出现次数小于 ``k``,任何包含它的子串都不可能合法,因此它可以作为分界点,把问题拆成左右两个独立区间;递归求两边最大值。若当前区间中每个出现过的字符都达到 ``k``,整个区间就是合法候选,直接返回区间长度。
这个分治不会漏掉答案:合法子串不可能跨过低频字符;若没有低频字符,当前区间本身已经满足条件。
C++ 实现
--------
.. code-block:: cpp
class Solution {
int solve(const std::string& s, int left, int right, int k) {
if (right - left < k) return 0;
std::array frequency{};
for (int i = left; i < right; ++i) {
++frequency[s[i] - 'a'];
}
for (int i = left; i < right; ++i) {
if (frequency[s[i] - 'a'] >= k) continue;
int next = i + 1;
while (next < right
&& frequency[s[next] - 'a'] < k) {
++next;
}
return std::max(solve(s, left, i, k),
solve(s, next, right, k));
}
return right - left;
}
public:
int longestSubstring(std::string s, int k) {
return solve(s, 0, static_cast(s.size()), k);
}
};
代码分析
--------
频次小于 ``k`` 的字符在当前区间中不能出现在任何合法答案里,连续低频字符可以一次跳过后再递归;没有分界点时整个区间一次返回。字母表固定为 26,平均递归层数下时间复杂度为 ``O(26n)`` 到 ``O(26n log n)`` 的范围,额外空间为 ``O(n)`` 递归栈最坏情况。