Leetcode 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.

Problem Analysis:

Firstly, let’s try to find some regularity.

If all letters appear k times at least, the result is the whole length of the string.

If some letter is appear less than k times, the valid substring can not across the letter. So we can find substring by split with the letter. then search in the substrings again and again. finally get the valid substrings.

Solution:

#include <limits>
#include <string>
#include <unordered_set>
#include <vector>
#include <algorithm>
using std::max;
using std::vector;
using std::string;
using std::unordered_set;
class Solution {
public:
  int longestSubstring(string s, int k) {
    int len = s.size();
    if (k < 1 || len < k) return 0;
    else if (k == 1) return len;
    vector<vector<int>> char_indexes(26, vector<int>());
    vector<int> valid_range(len, std::numeric_limits<int>::max());
    for (int i = 0; i < len; ++i) char_indexes[s[i] - 'a'].push_back(i);
    for (auto& array: char_indexes) {
      int array_len = array.size();
      for (int i = 0, j = i + k - 1; j < array_len; ++i, ++j)
        valid_range[array[i]] = array[j];
    }
    return longestSubstring(s, k, 0, len, valid_range);
  }
private:
  int longestSubstring(const string& s, int k, int start, int end,
                       const vector<int>& ranges) {
    if (start + k > end) return 0;
    int prev = start;
    int result = 0;
    unordered_set<char> chars;
    bool split_flag = false;
    for (int i = start; i < end; ++i) {
      if (chars.count(s[i]) == 0) {
        if (ranges[i] >= end) {
          split_flag = true;
          result = max(result, longestSubstring(s, k, prev, i, ranges));
          prev = i + 1;
          chars.clear();
        } else {
          chars.insert(s[i]);
        }
      }
    }
    if (split_flag)
      return max(result, longestSubstring(s, k, prev, end, ranges));
    return max(result, end - start);
  }
};

Time Complexity: O(n)

Space Complexity: O(n)

Test Cases:

Base Cases: all letters appear k times at least, some letters less than k times, all letters less than k times.

Corner Cases: string length < k, k < 1