Quick Overview

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.

Longest Substring Where Every Character Appears at Least K Times

Company: C3 AI

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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?

Overview: 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.

Read the full C3 AI Data Scientist interview experience this question came from

Given a lowercase English string s and an integer k, return the length of the longest contiguous substring in which every character that appears occurs at least k times. Return 0 if no such nonempty substring exists.

Constraints

  • 1 <= s.length <= 100000
  • s contains only lowercase English letters
  • 1 <= k <= 100000

Examples

Input: ('aaabb', 3)

Expected Output: 3

Explanation: The source example's substring aaa has its only character exactly three times.

Input: ('ababbc', 2)

Expected Output: 5

Explanation: The source example's substring ababb contains both a and b at least twice.

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.

Loading coding console...

Show the approach

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).