2021-8-21 395. 至少有 K 个重复字符的最长子串（分治）

本文主要是介绍2021-8-21 395. 至少有 K 个重复字符的最长子串（分治），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注：

题目：
给你一个字符串 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

题解：
思路及算法

如果一个字符 c 在 s 中出现的次数少于 k 次，那么 s 中所有的包含 c 的子字符串都不能满足题意。所以，应该在 s 的所有不包含 c 的子字符串中继续寻找结果：把 s 按照 c 分割（分割后每个子串都不包含 c），得到很多子字符串 t。
下一步要求 t 作为源字符串，求它的最长的满足题意的子字符串长度（到现在为止，我们把大问题分割为了小问题(s → t)）

复杂度分析
时间复杂度：O(N⋅∣Σ∣)，其中 N 为字符串的长度，Σ 为字符集，本题中字符串仅包含小写字母，因此∣Σ∣=26。由于每次递归调用都会完全去除某个字符，因此递归深度最多为∣Σ∣。

空间复杂度：O(∣Σ∣² )。递归的深度为O(∣Σ∣)，每层递归需要开辟 O(∣Σ∣) 的额外空间。

class Solution {
public:int dfs(string s,int l,int r,int k){if(l>r){return 0;}//统计[l,r]区间内个字母的出现次数map<char,int> charsnum;for(int i=l;i<=r;i++){charsnum[s[i]]++;}//找到[l,r]区间内出现次数不足k的字母splitchar split='1';for(auto c:charsnum){if(c.second>0&&c.second<k){split=c.first;}}//如果在[l,r]区间内没找到出现次数不足k的字母，则返回当前区间的长度if(split=='1'){return r-l+1;}//在split左右两侧进行分治int i=l;int res=0;while(i<=r){while(i<=r&&s[i]==split){i++;}if(i>r){break;}int start=i;while(i<=r&&s[i]!=split){i++;}res=max(res,dfs(s,start,i-1,k));}return res;}int longestSubstring(string s, int k) {int l=0;int r=s.size()-1;return dfs(s,l,r,k);}
};