395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is “aaa”, as ‘a’ is repeated 3 times.
Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

方法1: recursion

https://www.jianshu.com/p/6f066844b4a1
思路：

先统计一遍所有字符出现的次数，建立一个invalid set。 那么我们就可以将字符串分割为除去invalid字符外的一个个字串。另last永远指向字串的起点，用invalid.find(s[i]) != invalid.end()去确定终点。每次s.substr(last, i - last)，就是一个符合题意的字串。注意长度是i-last，i本身不包括在内，递归去检查每一个字串：此时之前满足>k的字母可能被切割后已经不满足。那么我们的递归终止条件就是1:字串已经是空，2. 字串全部满足要求。最后，退出循环后还要递归检查一次aabb也就是最后一个字串，才能完成。

易错点

1. 退出条件
2. 最后一段

Complexity

Time complexity:
Space complexity:

//aaaa c bbbbaaa d aabb
//l	   i           l
class Solution {
public:
    int longestSubstring(string s, int k) {
        int maxlen = 0;
        if (!s.size()){
            return maxlen;
        }
        vector<int> record(26, 0);
        
        for (char c: s){
            record[c - 'a']++;
        }
        unordered_set<char> invalid;
        for (int i = 0; i < s.size(); i ++){
            if (record[s[i] - 'a'] < k)
                invalid.insert(s[i]);
        }
        if (invalid.empty()){
            return s.size();
        }
        int last = 0;
        for (int i = 0; i < s.size(); i++){
            if (invalid.find(s[i]) != invalid.end()){
                maxlen = max(maxlen, longestSubstring(s.substr(last, i - last), k));
                last = i + 1;
            }
        }
        maxlen = max(maxlen, longestSubstring(s.substr(last), k));
        return maxlen;
    }
};