328. Longest Substring with At Least K Repeating Characters
You are given a string s of lowercase English letters and an integer k. Return the length of the longest substring of s in which every distinct character shows up at least k times.
A substring is a contiguous run of characters. Every character that appears inside the chosen substring must appear there k or more times — characters outside the substring don't matter. If no non-empty substring qualifies, return 0.
The classic trap: the "every character repeats enough" condition is not monotonic, so a naive two-pointer window doesn't work directly. There are two well-known ways around that.
Example 1:
Input: s = "aaabb", k = 3
Output: 3
Explanation: The substring "aaa" works: its only distinct character, 'a', appears 3 times. Any substring that includes a 'b' fails, because 'b' occurs only twice in the whole string.
Example 2:
Input: s = "ababbc", k = 2
Output: 5
Explanation: "ababb" qualifies: 'a' appears 2 times and 'b' appears 3 times, both at least k = 2. The final 'c' can never join a valid substring — it occurs once in the entire string.
Constraints:
- 1 ≤ s.length ≤ 10⁴
- s consists of lowercase English letters only
- 1 ≤ k ≤ 10⁵
Hints:
A character whose total count in the whole string is below k can never sit inside a valid substring. So the answer must live entirely between occurrences of such characters — that observation powers a divide-and-conquer solution.
For a sliding window: the raw condition isn't monotonic, but "at most h distinct characters" is. Try every h from 1 to 26; for each h keep a window with at most h distinct characters and check whether all h of them have reached k copies.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "aaabb", k = 3
Expected output: 3