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

难度 medium
给你一个字符串 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

解题思路1：这种解法还是比较接近暴力搜索的，简单地说就是从头开始向后遍历，然后用一个数组cnt记录每种字母出现的次数，mask表示在此轮遍历中是否满足所有字母出现的次数都大于k，满足则为0，不满足则为1，初始化为0，然后开始从i遍历这个字符串，在cnt中增加对应字母的个数，如果对应字母的个数小于k，则将mask对应的位置1，否则将mask对应的位置0，然后检查mask，如果mask==0，说明到当前遍历这个位置，没有出现那种个数小于k的字母，此时说明从i位置到当前这个位置，中间这段字符串是满足要求的，因此就更新res，同时用一个max_idx指示目前遍历到了哪个位置，当内循环（j）结束的时候，max_idx就是指向以i为起点，满足条件的最长字符串的终点，因此下一个i就是max_idx+1，这样直到i大于s.length()-k退出。返回res即可.

代码 t50 s24 java

class Solution {
    public int longestSubstring(String s, int k) {
        int res = 0, i = 0, len = s.length();
        while(i<=len-k){
            int mask = 0, max_idx = i;
            int[] cnt = new int[26];
            for(int j=i; j<len; j++){
                int t = s.charAt(j) - ‘a‘;
                cnt[t]++;
                if(cnt[t]<k) mask |= (1<<t);
                else mask &= (~(1<<t));
                if(mask==0){
                    res = Math.max(res, j-i+1);
                    max_idx = j;
                }
            }
            i = max_idx + 1;
        }
        return res;
    }
}

解题思路2：这个思路采用的是相对直观的思路，其实就是找到出现次数小于k的字母作为分割点，然后在分割出来的子字符串中找最大值，用一个数组cnt记录每个字母出现的次数，然后从头开始遍历字符串，如果某个字母出现的次数小于k，就截取max_idx到i之间这一段，然后进行递归，max_idx是上一次遍历时记录的出现次数小于k的字母的下一个位，也就是候选字符串的起点，因此如果当前的字母出现次数小于k时，需要将max_idx赋为i+1，此外，还需要用一个标志位来记录这个过程是否有切分字母串的操作，complete初始化为true，如果出现切分字母串，就将其赋为false，最后遍历结束，检查comlete，如果还是true，那说明当前字符串就没有出现分割的情况，因此整个字符串满足条件，直接返回len，否则说明字符串出现了分割，我们的for循环结束是遍历完整个字符串就结束，因此如果最后一个字母不是出现次数小于k的字母，那从max_idx到字符串结尾这一段并没有考虑进来，因此需要对这一段调用递归函数，然后和res取较大值，再返回。

代码 t92 s33 java

class Solution {
    public int longestSubstring(String s, int k) {
        int res = 0, max_idx = 0, len = s.length();
        boolean complete = true;
        int[] cnt = new int[26];
        for(int i=0; i<len; i++) cnt[s.charAt(i)-‘a‘]++;
        for(int i=0; i<len; i++){
            if(cnt[s.charAt(i)-‘a‘]<k){
                complete = false;
                res = Math.max(res, longestSubstring(s.substring(max_idx, i), k));
                max_idx = i + 1;
            }
        }
        return complete ? len : Math.max(longestSubstring(s.substring(max_idx, len), k), res);
    }
}

代码 t100 s60 cpp

class Solution {
public:
    int longestSubstring(string s, int k) {
        // 遍历获取每个字符的个数，用于判断是否小于k
        unordered_map<char, int> m;
        for (auto& c : s)
        {
            m[c]++;
        }

        // 遍历把字符串按照小于k的数量拆分成多段，分开来解决
        vector<int> splits;
        int n = s.size();
        for (int i = 0; i < n; ++i)
        {
            if (m[s[i]] < k)
            {
                splits.push_back(i);
            }
        }

        // 无需拆分，则返回整段字符串
        if (splits.size() <= 0)
        {
            return s.size();
        }

        // 返回最大长度
        int res = 0;
        int left = 0;
        for (int i = 0; i < splits.size(); i++)
        {
            // 长度不包含这个split无效字符
            int len = splits[i] - left;
            // 至少要大于k，否则肯定是不满足的
            if (len >= k && len > res)
            {
                // cout << "len:" << len << " " << splits[i] << endl;
                // 继续去找子串里最大值
                res = max(res, longestSubstring(s.substr(left, len), k));
            }
            left = splits[i] + 1;
        }
        // 考虑最后一段没考虑的情况
        if (left < n-1)
        {
            res = max(res, longestSubstring(s.substr(left, n-1-left+1), k));
        }

        return res;
    }
};

参考资料：
https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/cchao-100de-fen-zhi-jie-fa-by-ffreturn-uygu/
https://www.cnblogs.com/grandyang/p/5852352.html

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

原文：https://www.cnblogs.com/zhengxch/p/14731538.html