企业官网建设流程全解析

LeetCode 395. 至少有 K 个重复字符的最长子串

思路一：分治法（推荐，代码简洁）

核心思想：如果某个字符在区间内出现次数小于 k，那么它必然不能出现在答案子串中。以该字符为界，把区间劈成若干段，递归求解，取最大值。

classSolution{publicintlongestSubstring(Strings,intk){if(s==null||s.length()<k)return0;returndfs(s,0,s.length(),k);}privateintdfs(Strings,intl,intr,intk){if(r-l<k)return0;int[]cnt=newint[26];for(inti=l;i<r;i++){cnt[s.charAt(i)-'a']++;}// 找第一个出现次数 < k 的字符，用它做分割点for(inti=l;i<r;i++){intidx=s.charAt(i)-'a';if(cnt[idx]<k){// 跳过所有不合法字符，从下一个合法位置开始intj=i+1;while(j<r&&cnt[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){intn=s.length();intres=0;for(intt=1;t<=26;t++){int[]cnt=newint[26];intleft=0,right=0;inttotal=0;// 窗口内不同字符数量intless=0;// 出现次数 < k 的字符种类数while(right<n){intc=s.charAt(right)-'a';cnt[c]++;if(cnt[c]==1){total++;less++;}if(cnt[c]==k)less--;right++;// 不同字符种类超过 t，收缩左边界while(total>t){intd=s.charAt(left)-'a';cnt[d]--;if(cnt[d]==0){total--;less--;}if(cnt[d]==k-1)less++;left++;}if(less==0)res=Math.max(res,right-left);}}returnres;}}

· 时间复杂度：O(26 * n) = O(n)
· 空间复杂度：O(1)（常数数组）

测试用例

publicstaticvoidmain(String[]args){Solutionsol=newSolution();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) 线性、稳定 需要理解「枚举种类数」技巧

💡 面试建议：先讲分治法（容易想到），如果面试官追问能否优化到线性，再给出滑动窗口解法。