Katkat
Back

Longest Substring Where Every Character Appears at Least K Times

C3 AIData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

Find the longest substring in which every present character appears at least k times. Practice divide-and-conquer splitting, frequency reasoning, and fixed-alphabet complexity.

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.

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?

Hints

Hint 1

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.