Find substring where all chars appear at least k

You are given a string s and an integer k (1 ≤ k ≤ |s|). Return the length of the longest substring in which every distinct character occurs at least k times. If no such substring exists, return 0. Describe your algorithm, explain why it is correct, and analyze its time and space complexity. Discuss edge cases such as k = 1, k > |s|, and strings with all unique characters.

Longest Substring with At Least K Repeating Characters

You are given a string s and an integer k (1 ≤ k ≤ |s|). Return the length of the longest substring of s in which every distinct character occurs at least k times. If no such substring exists, return 0.

A valid substring is a contiguous slice of s; within that slice, each character that appears must appear at least k times. You want the longest such slice.

Examples

• s = "aaabb", k = 3 → 3. The substring "aaa" has every character (a) appearing 3 ≥ 3 times; "aaabb" fails because b appears only twice.
• s = "ababbc", k = 2 → 5. The substring "ababb" has a appearing 2 times and b appearing 3 times, both ≥ 2.

Edge cases to consider

• k = 1: every character trivially appears at least once, so the answer is len(s).
• k > |s|: no substring can have any character appear k times, so the answer is 0.
• All-unique characters with k > 1: no character repeats, so the answer is 0.

Constraints

• 1 <= len(s) (the string is non-empty in typical inputs; an empty string returns 0)
• 1 <= k <= len(s) per the prompt, though the solution also handles k > len(s) by returning 0
• s consists of lowercase (or general) characters
• Return 0 when no valid substring exists

Hints

1. If a character appears fewer than k times in the whole string, it can never be part of any valid substring — so any valid substring must lie entirely between occurrences of that character. This naturally suggests a divide-and-conquer split.
2. Count the frequency of each character. Pick a character whose total count is less than k and split the string on every occurrence of it; recurse on each resulting fragment and take the maximum.
3. Base cases: if k <= 1, the answer is len(s); if every character in the current fragment already appears at least k times, that whole fragment is valid and its length is the answer.
4. An alternative O(N) sliding-window approach fixes the number of distinct characters t (1..26) allowed in the window and slides a window keeping exactly t distinct chars, checking that each appears >= k times.