395. Longest Substring with At Least K Repeating Characters.md

395. Longest Substring with At Least K Repeating Characters

思路

给定一个只包含小写字母的字符串s和整数k，求s的子串中满足子串中的字母出现次数都不少于k的子串的最大长度。

思路一、暴力

此题可以用暴力解法，但是直接暴力可能会超时，需要稍微改进一点。我们如何判断每个字母出现次数是否不小于k呢， 如果我们用一个长为26的数组cnt记录每个字母的出现次数，然后需要每次遍历一遍这个数组来判断是否满足提交，效率不高。 由于只可能是26个小写字母，所以我们新增一个32位整数mask来记录某个字母是否是满足条件的， 若某一位为0则对应字母是满足条件的（即要么没这个字母要么这个字母出现次数不小于k），所以我们只需判断整个mask是否为0就可以判断是否全部满足条件了。

具体来讲，我们用两层循环，第一层循环为子串的左边界start，第二层循环则是子串的右边界end。 每次进入第二层循环时都需要初始化数组cnt和mask，在第二层循环内部我们需要更新mask并判断mask是否为0，若是即可尝试更新结果。

时间复杂度O(n^2)，空间复杂度O(1)。

如果只有小（大）写字母，即只有26个字符，那么用一个32为整数来进行记录一些bool状态是很常见的思路。

思路二、分治

此题可以考虑用分治法。那么要如何进行划分呢，由于要满足出现次数不小于k，我们可以考虑先统计每个字母的出现次数， 出现次数小于k的那些字母肯定不可能出现在合法子串中的，即可以将这些字母作为分界线对字符串s进行划分。递归出口就是每次字母出现次数都不小于k。

这应该是此题最好写的方法，亲测也是最快的（0ms）。

思路二、双指针

因为题目中限定了字符串中只有26个小写字母，所以最后满足题意的子串中的unique字母数一定是在范围[1, 26]内， 我们可以从1到26枚举unique字母数（记为cnt），对于每个cnt，维护一个窗口左右指针start和end，我们不断更新end和start，保持窗口内的子串的unique字符数（记为uniqueCnt）不超过cnt， 为此需要用一个大小为26的数组charCnt来记录窗口内每个字母的出现次数。

怎样更新start和end呢？我们让end不断加1更新，而start的更新需要视情况而定：

先判断end字符是否是一个全新的字符，若是那么需要让uniqueCnt加1，此时可能uniqueCnt超过cnt了，所以我们需要将start右移直到uniqueCnt不超过cnt。 每次更新好end和start后还需要判断窗口内每个字符串是否满足条件，若是应该尝试更新res。

外层循环固定26次，内存循环中end和start都是只可能往右不可能往左的，所以是线性复杂度的，所以总的时间复杂度也是线性的。

C++

思路一

class Solution {
public:
    int longestSubstring(string s, int k) {
        int start = 0, res = 0;
        for(int start = 0; start < s.size(); start++){
            int mask = 0; 
            vector<int>cnt(26, 0);
            for(int end = start; end < s.size(); end++){
                int c = s[end] - 'a';
                if(++cnt[c] >= k) mask &= (~(1 << c)); // 将对应位置0
                else mask |= (1 << c); // 将对应位置1
                
                if(!mask) res = max(res, end - start + 1);
            }
        }
        
        return res;
    }
};

思路二

class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0, n = s.size();
        
        vector<int>cnt(26, 0); // 统计每个字母的出现次数
        for(auto &c: s) cnt[c - 'a']++;
        
        int start = 0;
        bool tag = true;
        for(int i = 0; i < n; i++){
            if(cnt[s[i] - 'a'] < k){
                tag = false;
                if(i > start)
                  res = max(res, longestSubstring(s.substr(start, i - start), k));
                start = i + 1;
            }
        }
        // tag为true说明每个字母出现次数均不小于k
        return tag ? s.size() : max(res, longestSubstring(s.substr(start, n - start), k));
    }
};

思路三

class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0, n = s.size();
        for (int cnt = 1; cnt <= 26; ++cnt) {
            int start = 0, end = 0, uniqueCnt = 0;
            vector<int> charCnt(26);
            for(; end < n; end++){
                if (charCnt[s[end] - 'a']++ == 0) uniqueCnt++;
                
                while (uniqueCnt > cnt)
                    if (--charCnt[s[start++] - 'a'] == 0) uniqueCnt--;
                
                bool valid = true;
                for (int j = 0; j < 26; ++j)
                    if (charCnt[j] > 0 && charCnt[j] < k)
                        {valid = false; break;}
            
                if(valid) res = max(res, end - start + 1);                
            }
        }    
        return res;
    }
};