分治题目：至少有 K 个重复字符的最长子串

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题至少有 K 个重复字符的最长子串出处395. 至少有 K 个重复字符的最长子串难度6 级题目描述要求给定一个字符串s \texttt{s}s和一个整数k \texttt{k}k找到s \texttt{s}s中的每个字符出现次数都大于等于k \texttt{k}k的最长子串返回该子串的长度。示例示例 1输入s aaabb, k 3 \texttt{s aaabb, k 3}s aaabb, k 3输出3 \texttt{3}3解释最长子串为aaa \texttt{aaa}aaa其中‘a’ \texttt{a}‘a’重复了3 \texttt{3}3次。示例 2输入s ababbc, k 2 \texttt{s ababbc, k 2}s ababbc, k 2输出5 \texttt{5}5解释最长子串为ababb \texttt{ababb}ababb其中‘a’ \texttt{a}‘a’重复了2 \texttt{2}2次‘b’ \texttt{b}‘b’重复了3 \texttt{3}3次。数据范围1 ≤ s.length ≤ 10 4 \texttt{1} \le \texttt{s.length} \le \texttt{10}^\texttt{4}1≤s.length≤104s \texttt{s}s仅由小写英语字母组成1 ≤ k ≤ 10 5 \texttt{1} \le \texttt{k} \le \texttt{10}^\texttt{5}1≤k≤105解法思路和算法为方便表述将每个字符出现次数都大于等于k kk的子串称为「符合要求的子串」。为了得到字符串s ss中的符合要求的最长子串需要统计字符串s ss中的每个字符的出现次数并判断每个字符是否可能出现在符合要求的子串中。如果一个字符的出现次数小于k kk则该字符不可能出现在符合要求的子串中。每个出现次数小于k kk的字符所在的下标都是字符串s ss的一个分割下标将所有的分割下标按升序排序之后相邻两个分割下标之间的部分为一个子串继续对每个子串寻找符合要求的最长子串。将字符串s ss分割成多个子串之后对于每个子串可以使用相同的方法寻找符合要求的最长子串这是一个递归分治的过程。分治的终止条件是当前子串中的每个字符的出现次数都大于等于k kk此时符合要求的最长子串为当前子串。其余情况下每个出现次数小于k kk的字符所在的下标都是一个分割下标根据分割下标将当前子串分割成多个更小的子串之后对于每个更小的子串递归地寻找符合要求的最长子串。从字符串s ss开始递归分治对字符串s ss操作结束之后即可得到符合要求的最长子串的长度。实现方面有一处可以优化。如果当前子串被分割之后其中的一个更小的子串的长度小于等于已知的符合要求的最长子串的长度则该更小的子串中一定不存在长度更大的符合要求的子串因此不需要对该更小的子串寻找符合要求的最长子串。代码classSolution{publicintlongestSubstring(Strings,intk){returnlongestSubstring(s,0,s.length()-1,k);}publicintlongestSubstring(Strings,intstart,intend,intk){int[]countsnewint[26];for(intistart;iend;i){counts[s.charAt(i)-a];}ListIntegersplitIndicesnewArrayListInteger();for(intistart;iend;i){if(counts[s.charAt(i)-a]k){splitIndices.add(i);}}splitIndices.add(end1);if(splitIndices.size()1){returnend-start1;}intmaxLength0;intleft0;for(intsplitIndex:splitIndices){if(splitIndex-leftmaxLength){maxLengthMath.max(maxLength,longestSubstring(s,left,splitIndex-1,k));}leftsplitIndex1;}returnmaxLength;}}复杂度分析时间复杂度O ( n × ∣ Σ ∣ ) O(n \times |\Sigma|)O(n×∣Σ∣)其中n nn是字符串s ss的长度Σ \SigmaΣ是字符集这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。由于每次递归调用都会至少排除一个字母因此递归调用栈共有O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)层每一层需要O ( n ) O(n)O(n)的时间遍历字符串s ss一次因此时间复杂度是O ( n × ∣ Σ ∣ ) O(n \times |\Sigma|)O(n×∣Σ∣)。空间复杂度O ( ∣ Σ ∣ 2 ) O(|\Sigma|^2)O(∣Σ∣2)其中Σ \SigmaΣ是字符集这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。由于每次递归调用都会至少排除一个字母因此递归调用栈共有O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)层每一层的哈希表需要O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)的空间因此空间复杂度是O ( ∣ Σ ∣ 2 ) O(|\Sigma|^2)O(∣Σ∣2)。