Longest Substring Where Every Character Appears at Least K Times

Given a string s of lowercase English letters and an integer k, implement:

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

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?

Longest Substring with Repeating Characters

Hints

1. The alphabet bounds the number of distinct characters in any window to 26.
2. For each possible distinct-character count, maintain a window and track how many present characters have reached frequency k.

Approach

There are only 26 possible distinct-character counts. For each target count from 1 through 26, scan with a sliding window that contains at most that many distinct characters. The frequency array supports two exact counters: unique is the number of characters present, and at_least_k is the number whose frequency has reached k. A window is valid precisely when both counters equal target_unique. When too many distinct characters are present, advance the left boundary and update both counters before continuing. For correctness, take any valid substring and let u be its number of distinct characters. During the pass with target_unique equal to u, the window never discards its left boundary merely for having those u characters; as its right boundary reaches the substring's end, the scan considers a window containing that candidate and records a length at least as large. Conversely, a recorded window has exactly target_unique characters and all of them are counted by at_least_k, so every recorded window satisfies the condition. The maximum recorded length is therefore optimal. If k exceeds the whole string length, no nonempty substring can qualify.

• Time complexity: O(26 * n), which is O(n) for the fixed lowercase-English alphabet.
• Space complexity: O(26), which is O(1).