博客

分治的思想

首先我们遍历整个字符串，那么如果有字符在整个字符串中出现的次数都少于k，那么最终的答案字串一定不包含该字符。由此，我们将字符串s按照这种不可能出现的字符为分隔线，分为若干个字串来递归分析，直到有一个字串中所有的字符都满足出现次数不少于k的要求。

优化：建立一个全局二维数组，统计下标 i 之前字符 j 出现了多少次，这样就只需要遍历一遍字符串就够了。之后通过前缀和的思想就可以直到 l – r 的范围内每个字符出现了多少次。（因为不优化就已经是0ms，所以我就没有尝试）

自己的（0ms）

class Solution {
    public int longestSubstring(String s, int k) {
        if(s.length() < k)
            return 0;
        int[] num = new int[26];
        for(int i = 0; i < s.length(); i++){
            num[s.charAt(i) - 'a'] ++; 
        }
        int l = 0,ans = 0;
        for(int i = 0; i < s.length(); i++){
            if(num[s.charAt(i) - 'a'] < k){
                ans = Math.max(ans,longestSubstring(s.substring(l,i),k));
                l = i + 1;
            }
        }
        if(l == 0)
            return s.length();
        return Math.max(ans,longestSubstring(s.substring(l,s.length()),k));
    }
}