Longest Substring Where Every Character Appears at Least K Times

Given a string `s` of lowercase English letters and an integer `k`, implement: ```text longest_repeating_substring(s: str, k: int) -> int ``` Return the length of the longest contiguous substring in which every character that appears in the substring appears at least `k` times. ### Constraints - `1 <= len(s) <= 100_000` - `1 <= k <= 100_000` - `s` contains only `a` through `z`. - Return zero when no nonempty substring satisfies the condition. ### Clarifications - The frequency requirement is evaluated inside the chosen substring, not across the full input. - Characters absent from the substring impose no requirement. - When `k == 1`, the entire string is valid. ```hint Split on an impossible character Within a candidate segment, any character whose total segment frequency is below `k` cannot occur in a valid answer spanning that character. ``` ### Examples ```text Input: s = "aaabb", k = 3 Output: 3 Explanation: "aaa" is valid. Input: s = "ababbc", k = 2 Output: 5 Explanation: "ababb" is valid. ``` ### Evaluation Focus - Correct divide-and-conquer segmentation or another provably bounded method. - Proper handling of segments that are already valid and characters below the threshold. - Empty segments, large `k`, and repeated split characters. - A clear time-complexity argument for the fixed 26-character alphabet. ### Extension How would the complexity change for an unbounded Unicode alphabet?