395

395. Longest Substring with At Least K Repeating Characters (Medium)

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

 

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

 

Constraints:

• 1 <= s.length <= 104
• s consists of only lowercase English letters.
• 1 <= k <= 105

Related Topics:
Divide and Conquer, Recursion, Sliding Window

Solution 1. Sliding Window + Recursion

// OJ: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int longestSubstring(string s, int k) {
        int cnt[26] = {}, ans = 0; // `cnt[i]` is the remaining count of characters `'a' + i` that haven't been added into the sliding window
        for (char c : s) cnt[c - 'a']++;
        for (int i = 0, N = s.size(); i < N; ) { // i is the starting point.
            int added[26] = {}; // the characters in range [i, j) are counted in `added`.
            while (i < N && cnt[s[i] - 'a'] < k) ++i; // skip those characters with counts less than k because they won't show up in the answer
            int j = i; // j is the ending point
            while (j < N && cnt[s[j] - 'a'] + added[s[j] - 'a'] >= k) {
                added[s[j] - 'a']++; // add `s[j]` into the window. Decrement `cnt[s[j] - 'a']` since this occurrence is used.
                cnt[s[j] - 'a']--;
                ++j;
            }
            bool valid = true;
            for (int n : added) {
                if (n && n < k) {
                    valid = false;
                    break;
                }
            }
            if (valid) ans = max(ans, j - i); // if this window is valid, update answer
            else ans = max(ans, longestSubstring(s.substr(i, j - i), k)); // otherwise, solve recursively
            i = j;
        }
        return ans;
    }
};

Solution 2. Sliding Window + Recursion

// OJ: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/57134/two-short-c-solutions-3ms-and-6ms
class Solution {
private:
    int longestSubstring(string &s, int k, int begin, int end) {
        int cnt[26] = {};
        for (int i = begin; i < end; ++i) cnt[s[i] - 'a']++;
        int i = begin, ans = 0;
        while (i < end) {
            while (i < end && cnt[s[i] - 'a'] < k) ++i;
            int j = i;
            while (j < end && cnt[s[j] - 'a'] >= k) ++j;
            if (i == begin && j == end) return end - begin;
            ans = max(ans, longestSubstring(s, k, i, j));
            i = j;
        }
        return ans;
    }
public:
    int longestSubstring(string s, int k) {
        return longestSubstring(s, k, 0, s.size());
    }
};