We need to find the longest substring where every character that appears in it appears at least k times. This is not about finding a single character that repeats k times. Every character in the substring must meet the threshold. If even one character falls short, the entire substring is invalid.

The "at least k" constraint applies per-character within the substring, not globally. A character that appears 100 times in the full string might appear only once in a particular substring, disqualifying it. And unlike sliding window problems where the constraint can be checked incrementally as the window grows, here the validity of a window depends on all characters at once, so adding one character can invalidate a window that was previously valid.

One property drives most of the solutions: any character that appears fewer than k times in the entire string can never belong to any valid substring. Such characters act as splitting points that divide the string into segments. The answer must lie entirely within one of those segments. This property leads directly to a divide and conquer approach, and to a sliding window variant that fixes the number of distinct characters.

Key Constraints:

Intuition

Check every possible substring and test whether it satisfies the constraint. For each substring, count the frequency of every character and verify that all characters appear at least k times. Pick every starting index, extend to every ending index, count frequencies as you extend, and track the longest substring that passes.

Algorithm

Visualization and Code

This checks every substring independently and ignores the structure of the problem. The next approach uses the low-frequency characters to split the string into smaller independent subproblems.

Intuition

If a character appears in s fewer than k times total, it can never be part of any valid substring, so every valid substring must avoid it entirely. That character splits the string into segments, and the answer lies entirely within one of those segments.

This gives a recursive strategy. Count character frequencies for the current string. Find a character that appears fewer than k times. Split the string at every occurrence of that character, then recursively solve each segment. The answer is the maximum across all segments.

If every character in the current string already meets the threshold, the entire string is valid and we return its length. That is the base case.

Algorithm

Visualization and Code

The divide and conquer approach is efficient but recursive. The next approach solves the problem iteratively with a sliding window. The obstacle is the shrink condition, which the approach removes by fixing the number of distinct characters allowed in the window.

Intuition

A standard sliding window fails here because there is no monotonic shrink condition. When the window expands and a new character enters with frequency below k, shrinking from the left could remove a character that was already valid, so the window length is not a function we can grow and shrink greedily.

Adding one constraint fixes this. Instead of asking for the longest valid substring directly, ask for the longest valid substring that contains exactly t distinct characters. Fixing t gives a clean shrink condition: whenever the window holds more than t distinct characters, shrink from the left until it holds exactly t again. When the window holds exactly t distinct characters and all t of them have frequency at least k, the window is valid.

A valid answer has some number of distinct characters between 1 and 26, so running this windowed scan once for each t from 1 to 26 covers every case. Each scan is O(n), so the total is O(26n) = O(n).

Algorithm

Visualization and Code