395. Longest Substring with At Least K Repeating Characters -M ！！

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.

A:

就是挨个数，如果某个字母不满足，则将其前后分开。递归  （pass）

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.length()<k)
            return 0;        // return 0 if does not contains such a string
        vector<int> C(26,0);
        for(auto ch : s)
            C[ch-'a']++;
        for(int i =0;i<s.length();++i)
        {
            int count = C[s[i]-'a'];
            if((count>0 and count < k)) // if not include this letter, exclude it and 
            {
                int tmp = longestSubstring(s.substr(0, i), k ); // will omit the last substring
                int tmp2 = longestSubstring(s.substr(i+1), k ); // will omit the last substring
                return max(tmp, tmp2);
            }
        }
        return s.length();
    }
};

• Time complexity:O(N*lg(N))

改进算法： 

Approach 2 : Sliding Window

Complexity

• Time complexity:O(N)

• Space complexity:O(1)