Longest Substring with At Least K Repeating Characters
Medium · Sliding Window · Explanation and code example
Sliding Windows with a Fixed Distinct Count
How it works
The lowercase alphabet has only 26 possibilities for the number of distinct letters in a valid substring. For each possible count, maintain a window with at most that many distinct letters. A window qualifies when every present letter has reached frequency k.
Steps
- Try each allowed distinct-letter count from one to 26.
- Expand the window and shrink when too many distinct letters appear.
- Update the answer when all distinct letters have frequency at least k.
Complexity
- Time: O(26n), or O(n) for a fixed lowercase alphabet.
- Space: O(26).
Things to watch for
- Update threshold counts when frequency crosses k in either direction.
- A total window length >= k does not guarantee each letter qualifies.
- The fixed-alphabet bound is part of this approach.
Python code example
import collections
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
def longestSubstringWithNUniqueLetters(n: int) -> int:
res = 0
uniqueLetters = 0 # the number of unique letters
lettersHavingKFreq = 0 # the number of letters having frequency >= k
count = collections.Counter()
l = 0
for r, c in enumerate(s):
count[c] += 1
if count[c] == 1:
uniqueLetters += 1
if count[c] == k:
lettersHavingKFreq += 1
while uniqueLetters > n:
if count[s[l]] == k:
lettersHavingKFreq -= 1
count[s[l]] -= 1
if count[s[l]] == 0:
uniqueLetters -= 1
l += 1
# Since both the number of unique letters and the number of letters
# having frequency >= k are equal to n, this is a valid window.
if lettersHavingKFreq == n: # Implicit: uniqueLetters == n
res = max(res, r - l + 1)
return res
return max(longestSubstringWithNUniqueLetters(n)
for n in range(1, 27))
C++ code example
class Solution {
public:
int longestSubstring(string s, int k) {
int ans = 0;
for (int n = 1; n <= 26; ++n)
ans = max(ans, longestSubstringWithNUniqueLetters(s, k, n));
return ans;
}
private:
int longestSubstringWithNUniqueLetters(const string& s, int k, int n) {
int res = 0;
int uniqueLetters = 0; // the number of unique letters
int lettersHavingKFreq = 0; // the number of letters having frequency >= k
vector<int> count(26);
for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s[r] - 'a'] == 1)
++uniqueLetters;
if (count[s[r] - 'a'] == k)
++lettersHavingKFreq;
while (uniqueLetters > n) {
if (count[s[l] - 'a'] == k)
--lettersHavingKFreq;
if (--count[s[l] - 'a'] == 0)
--uniqueLetters;
++l;
}
// Since both the number of unique letters and the number of letters
// having frequency >= k are equal to n, this is a valid window.
if (lettersHavingKFreq == n) // Implicit: uniqueLetters == n
res = max(res, r - l + 1);
}
return res;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.