Longest Substring with At Least K Repeating Characters
Medium · Sliding Window · Hash Table · String · Divide and Conquer · Sliding Window
Problem
Given a string s and an integer k, return the length of the longest substring in which every character that appears does so at least k times.
If no such substring exists, return 0.
Examples
Input: s = "aaabbc", k = 2 Output: 5
In "aaabb", a appears three times and b twice. c appears only once in the whole string, so no valid substring contains it.
Input: s = "xyz", k = 2 Output: 0
Every character appears only once.
Input: s = "ababbcaaab", k = 3 Output: 3
The single c cannot be used. On its left, "ababb" has only two a's, and without the a's only short runs of b are left. On its right, "aaa" works but "aaab" has one b.
Constraints
- 1 <= len(s) <= 10^4
- s consists of lowercase English letters
- 1 <= k <= 10^5
Approaches
- Every start, extend with running counts — time O(n²), space O(1): 26 counts
Follow-up
There is also a divide-and-conquer solution: any letter that appears fewer than k times in the current string cannot be in the answer, so split the string at every such letter and solve each piece. Each level of splitting removes at least one letter from the pieces, so there are at most 26 levels: O(26 · n) as well.
Related problems
Start free on Cariara · Coding problems · System design studio
