Longest Substring with At Least K Repeating Characters - Video Solutions

Problem Overview: Given a string s and an integer k, find the length of the longest substring where every character appears at least k times. The substring must be contiguous, and any character that appears fewer than k times invalidates that segment.

Approach 1: Divide and Conquer (O(n log n) time, O(n) space)

This strategy recursively splits the string around characters that cannot be part of a valid substring. First, count the frequency of each character in the current segment using a hash map. Any character whose frequency is less than k cannot appear in a valid result. Use such characters as split points and recursively evaluate the left and right substrings. If every character in the segment already satisfies the constraint, the entire segment length is valid. The key insight: invalid characters partition the problem into smaller independent substrings. This method works well because each recursive call processes smaller segments and avoids checking impossible candidates repeatedly. It heavily relies on frequency counting with a hash table and recursion typical of divide and conquer problems.

Approach 2: Sliding Window with Variable Unique Character Constraint (O(26 * n) time, O(1) space)

This approach iterates over possible counts of unique characters and uses a sliding window to maintain substrings that satisfy the constraint. For each target number of distinct characters (1 through 26 for lowercase letters), expand the window with two pointers. Track character frequencies and maintain two counters: the number of unique characters and the number of characters that appear at least k times. When the unique count exceeds the target, shrink the window from the left. When both counts match, the window represents a valid substring where every character repeats at least k times. This converts the global constraint into a manageable window condition and systematically explores all valid configurations. The technique combines frequency tracking with the sliding window pattern.

Recommended for interviews: The sliding window approach demonstrates stronger algorithmic control and typically achieves near-linear performance. Interviewers often expect candidates to recognize that brute force substring checks are inefficient and then transition to either divide-and-conquer splitting or a constrained sliding window. Showing the recursive split first proves understanding of the constraint, while implementing the sliding window highlights optimization skills.