LeetCode 395. Longest Substring with At Least K Repeating Characters

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size(), ans = 0;
        for (int cnt = 1; cnt <= 26; ++cnt) { // there could be [1..26] diff letters.
            int left = 0, right = 0, uniqueCnt = 0;
            int charCnt[26] = {0};
            while (right < n) {
                bool valid = true;
                if (charCnt[s[right++] - 'a']++ == 0)
                    ++uniqueCnt;
                while (uniqueCnt > cnt)
                    if (--charCnt[s[left++] - 'a'] == 0)
                        --uniqueCnt;
                for (int j = 0; j < 26; ++j)
                    if (charCnt[j] > 0 && charCnt[j] < k) {
                        valid = false;
                        break;
                    }
                if (valid)
                    ans = max(ans, right - left);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size(), m[26] = {0}, left = 0, ans = 0;
        bool valid = true;
        for (char c : s)
            ++m[c - 'a'];
        for (int right = 0; right < n; ++right)
            if (m[s[right] - 'a'] < k) {
                ans = max(ans, longestSubstring(s.substr(left, right - left), k));
                valid = false;
                left = right + 1;
            }
        return valid ? n : max(ans, longestSubstring(s.substr(left, n - left), k));
    }
};