Skip to content

395. Longest Substring with At Least K Repeating Characters 👍

  • Time: $O(n)$
  • Space: $O(26)$
 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
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int longestSubstring(string s, int k) {
    int ans = 0;

    for (int n = 1; n <= 26; ++n)
      ans = max(ans, longestSubstringWithNUniqueCharacters(s, k, n));

    return ans;
  }

 private:
  int longestSubstringWithNUniqueCharacters(const string& s, int k, int n) {
    int ans = 0;
    int uniqueChars = 0;  // # of unique chars in window
    int noLessThanK = 0;  // # of chars >= k in window
    vector<int> count(128);

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (count[s[r]] == 0)
        ++uniqueChars;
      if (++count[s[r]] == k)
        ++noLessThanK;
      while (uniqueChars > n) {
        if (count[s[l]] == k)
          --noLessThanK;
        if (--count[s[l]] == 0)
          --uniqueChars;
        ++l;
      }
      if (noLessThanK == n)  // Unique chars also == n
        ans = max(ans, r - l + 1);
    }

    return ans;
  }
};

 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
27
28
29
30
31
32
33
34
35
class Solution {
  public int longestSubstring(String s, int k) {
    int ans = 0;

    for (int n = 1; n <= 26; ++n)
      ans = Math.max(ans, longestSubstringWithNUniqueCharacters(s, k, n));

    return ans;
  }

  private int longestSubstringWithNUniqueCharacters(final String s, int k, int n) {
    int ans = 0;
    int uniqueChars = 0; // Unique chars in current substring s[l..r]
    int noLessThanK = 0; // # of chars >= k
    int[] count = new int[128];

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (count[s.charAt(r)] == 0)
        ++uniqueChars;
      if (++count[s.charAt(r)] == k)
        ++noLessThanK;
      while (uniqueChars > n) {
        if (count[s.charAt(l)] == k)
          --noLessThanK;
        if (--count[s.charAt(l)] == 0)
          --uniqueChars;
        ++l;
      }
      if (noLessThanK == n) // Unique chars also == n
        ans = Math.max(ans, r - l + 1);
    }

    return ans;
  }
}