LeetCode 395. 至少有 K 个重复字符的最长子串思路一分治法推荐代码简洁核心思想如果某个字符在区间内出现次数小于 k那么它必然不能出现在答案子串中。以该字符为界把区间劈成若干段递归求解取最大值。classSolution{publicintlongestSubstring(Strings,intk){if(snull||s.length()k)return0;returndfs(s,0,s.length(),k);}privateintdfs(Strings,intl,intr,intk){if(r-lk)return0;int[]cntnewint[26];for(intil;ir;i){cnt[s.charAt(i)-a];}// 找第一个出现次数 k 的字符用它做分割点for(intil;ir;i){intidxs.charAt(i)-a;if(cnt[idx]k){// 跳过所有不合法字符从下一个合法位置开始intji1;while(jrcnt[s.charAt(j)-a]k)j;returnMath.max(dfs(s,l,i,k),dfs(s,j,r,k));}}// 所有字符出现次数都 kreturnr-l;}}· 时间复杂度平均 O(n log n)最坏 O(n²)· 空间复杂度递归栈 O(n)思路二滑动窗口O(26n)面试进阶核心思想固定窗口内允许出现的不同字符种类数 t枚举 t 1 ~ 26。在 total t 的前提下用双指针滑窗并维护一个 less 表示出现次数 k 的字符种类数。当 less 0 时窗口合法。classSolution{publicintlongestSubstring(Strings,intk){intns.length();intres0;for(intt1;t26;t){int[]cntnewint[26];intleft0,right0;inttotal0;// 窗口内不同字符数量intless0;// 出现次数 k 的字符种类数while(rightn){intcs.charAt(right)-a;cnt[c];if(cnt[c]1){total;less;}if(cnt[c]k)less--;right;// 不同字符种类超过 t收缩左边界while(totalt){intds.charAt(left)-a;cnt[d]--;if(cnt[d]0){total--;less--;}if(cnt[d]k-1)less;left;}if(less0)resMath.max(res,right-left);}}returnres;}}· 时间复杂度O(26 * n) O(n)· 空间复杂度O(1)常数数组测试用例publicstaticvoidmain(String[]args){SolutionsolnewSolution();System.out.println(sol.longestSubstring(aaabb,3));// 3 (aaa)System.out.println(sol.longestSubstring(ababbc,2));// 5 (ababb)System.out.println(sol.longestSubstring(aaabbb,3));// 6}对比解法 时间复杂度 优点 缺点分治 平均 O(n log n) 思路直观、代码短 最坏 O(n²)滑动窗口 O(26n) 线性、稳定 需要理解「枚举种类数」技巧 面试建议先讲分治法容易想到如果面试官追问能否优化到线性再给出滑动窗口解法。