Longest Substring with At Least K Repeating Characters LeetCode solution in C++

1
/*
2
    https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
3

4
    TC: O(26 * n) ~ O(n)
5
    SC: O(26)
6

7
    At a glance even though it seems like it can be solved with sliding window,
8
   it's hard to come up with window condition with the traditional sliding
9
   window approach. Problem is what will be your valid window criteria? Since we
10
   dont know how many unique chars might come up in the window, we dont know
11
   whether we should shrink the window or even though few of the unique chars
12
   have at least k instances.
13

14
    So we change the problem a bit. We change the window criteria:
15
    Find the max length window with atmost X unique chars. This is easier
16
   problem to deal with. The shrinking window criteria is clear, also we also
17
   keep track of chars in the window with frequency >= k while solving this
18
   problem.
19

20
    Now since we are limiting the no. of unique chars, we need to run the above
21
   |unique chars in s| times.
22
*/
23
class Solution {
24
 public:
25
  int uniqueChars(string &s) {
26
    unordered_set<char> chars(s.begin(), s.end());
27
    return chars.size();
28
  }
29

30
  int longestSubstring(string s, int k) {
31
    // find the no. of unique chars in string
32
    int max_unique_chars = uniqueChars(s);
33
    int max_len = 0, n = s.size();
34

35
    for (int curr_unique_chars = 1; curr_unique_chars <= max_unique_chars; curr_unique_chars++) {
36
      int start = 0, end = 0;
37
      int atleast_k = 0;
38
      unordered_map<char, int> freq;
39

40
      // Process the max length window with at max curr_unique_chars unique
41
      // chars
42
      while (end < n) {
43
        // attempt window expansion
44
        if (++freq[s[end]] == k) ++atleast_k;
45
        ++end;
46

47
        // shrink the window if unique chars exceeds the limit
48
        while (freq.size() > curr_unique_chars && start <= end) {
49
          // Current char contributed to atleast_k count, so it's count will be
50
          // lesser than k now
51
          if (freq[s[start]] == k) --atleast_k;
52
          if (--freq[s[start]] == 0) freq.erase(s[start]);
53
          ++start;
54
        }
55
        // If the current window has required no. of chars and it also each
56
        // unique chars have atleast k instances
57
        if (freq.size() == curr_unique_chars && atleast_k == freq.size())
58
          max_len = max(max_len, end - start);
59
      }
60
    }
61
    return max_len;
62
  }
63
};