Longest Substring With At Least K Repeating Characters Solution
Longest Substring With At Least K Repeating Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Substring With At Least K Repeating Characters is a medium coding problem on strings, sliding window and divide and conquer, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Sliding Window, Divide and Conquer
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s and an integer k, return the length of the longest substring in which every character appears at least k times.
If no such substring exists, return 0.
Example 1
Input: s = "aaabb", k = 3
Output: 3
Explanation: "aaa" is the longest — b appears only twice.
Example 2
Input: s = "ababbc", k = 2
Output: 5
Explanation: "ababb" has a three times and b twice.
Example 3
Input: s = "codekairo", k = 2
Output: 0
Explanation: Only o repeats, and never with anything else around it.
Constraints
1 <= s.length <= 100001 <= k <= 100000s consists of lowercase English letters.
Hints for Longest Substring With At Least K Repeating Characters
Hint 1
A plain sliding window does not work directly — the 'every character appears at least k times' condition is not monotone as the window grows.
Hint 2
Fix the number of distinct characters the window may hold. Now the window is monotone again and two pointers apply.
Hint 3
There are only 26 possible values for that number, so try each one.
How to solve Longest Substring With At Least K Repeating Characters
The condition is not monotone, so a single sliding window fails. Adding a constraint fixes it: for a fixed number t of distinct characters, 'at most t distinct' is monotone, so a window can be maintained. Trying t = 1 .. 26 covers every possible answer.
Approach
- For each
tfrom 1 to 26, run a sliding window overs. - Track per-character counts,
unique(distinct characters in the window) andatLeastK(how many of them reachk). - Shrink from the left while
unique > t. - Whenever
unique == tandatLeastK == t, every character in the window qualifies — record the window length.
Why it works
Any optimal substring has some number of distinct characters t* between 1 and 26; on the pass with t = t* the window can grow to exactly that substring, because the shrink rule only triggers when the distinct count exceeds t*. So the maximum over all 26 passes is the true answer.
Complexity
- Time —
O(26 · n) - Space —
O(26)
Pitfalls
- A single unconstrained window is the classic wrong answer — growing it can break the condition and shrinking it can fix it, so neither pointer moves monotonically.
- Recording the window when
atLeastK == tbutunique < tcounts a window that has not yet reached the target distinct count. - The divide-and-conquer solution — split on any character with fewer than
koccurrences and recurse — is the other standard route.
Reference solution
Python
def longestSubstring(s: str, k: int) -> int:
n = len(s)
best = 0
for target in range(1, 27):
count = [0] * 26
left = unique = at_least_k = 0
for right in range(n):
c = ord(s[right]) - 97
if count[c] == 0:
unique += 1
count[c] += 1
if count[c] == k:
at_least_k += 1
while unique > target:
d = ord(s[left]) - 97
if count[d] == k:
at_least_k -= 1
count[d] -= 1
if count[d] == 0:
unique -= 1
left += 1
if unique == target and at_least_k == target:
best = max(best, right - left + 1)
return bestJava
public static int longestSubstring(String s, int k) {
int n = s.length(), best = 0;
for (int target = 1; target <= 26; target++) {
int[] count = new int[26];
int left = 0, unique = 0, atLeastK = 0;
for (int right = 0; right < n; right++) {
int c = s.charAt(right) - 'a';
if (count[c] == 0) unique++;
count[c]++;
if (count[c] == k) atLeastK++;
while (unique > target) {
int d = s.charAt(left) - 'a';
if (count[d] == k) atLeastK--;
count[d]--;
if (count[d] == 0) unique--;
left++;
}
if (unique == target && atLeastK == target) best = Math.max(best, right - left + 1);
}
}
return best;
}C++
int longestSubstring(string s, int k) {
int n = (int) s.size(), best = 0;
for (int target = 1; target <= 26; target++) {
vector<int> count(26, 0);
int left = 0, unique = 0, atLeastK = 0;
for (int right = 0; right < n; right++) {
int c = s[right] - 'a';
if (count[c] == 0) unique++;
count[c]++;
if (count[c] == k) atLeastK++;
while (unique > target) {
int d = s[left] - 'a';
if (count[d] == k) atLeastK--;
count[d]--;
if (count[d] == 0) unique--;
left++;
}
if (unique == target && atLeastK == target) best = max(best, right - left + 1);
}
}
return best;
}JavaScript
var longestSubstring = function(s, k) {
var n = s.length, best = 0;
for (var target = 1; target <= 26; target++) {
var count = [];
for (var t = 0; t < 26; t++) count.push(0);
var left = 0, unique = 0, atLeastK = 0;
for (var right = 0; right < n; right++) {
var c = s.charCodeAt(right) - 97;
if (count[c] === 0) unique++;
count[c]++;
if (count[c] === k) atLeastK++;
while (unique > target) {
var d = s.charCodeAt(left) - 97;
if (count[d] === k) atLeastK--;
count[d]--;
if (count[d] === 0) unique--;
left++;
}
if (unique === target && atLeastK === target && right - left + 1 > best) best = right - left + 1;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sliding Window Technique