Longest Substring with At Least K Repeating Characters

Longest Substring with At Least K Repeating Characters

What is this problem about?

This problem gives you a string s and an integer k. You need to find the length of the longest substring where every character inside that substring appears at least k times. For example, if s = "ababbc" and k = 2, the longest substring is "ababb", because both 'a' and 'b' appear at least 2 times within it.

Why is this asked in interviews?

This is a classic recursive string problem. It is heavily favored by interviewers because it elegantly breaks standard Sliding Window templates. A standard sliding window struggles here because adding a character might fix one constraint but break another, making it hard to know when to shrink. It forces candidates to pivot to a Divide and Conquer mindset, demonstrating algorithmic flexibility.

Algorithmic pattern used

The most intuitive approach is Divide and Conquer. You count the frequencies of all characters in the string. Any character that appears fewer than k times in the entire string cannot possibly be part of a valid substring. Therefore, this character acts as a "split point" or "poison". You split the string around these invalid characters and recursively call your function on the resulting sub-segments, returning the maximum valid length found.

Example explanation

String s = "ababbc", k = 2.

1. Count frequencies: a: 2, b: 3, c: 1.
2. The character 'c' appears only once, which is $< 2$. It is invalid.
3. We split the string at 'c'. The only sub-segment is "ababb".
4. Recursive call on "ababb":
   • Count frequencies: a: 2, b: 3.
   • Are there any characters with count $< 2$? No! All characters appear at least k times.
5. This segment is perfectly valid. We return its length: 5.

Common mistakes candidates make

A major pitfall is attempting a pure $O(N)$ sliding window without limiting the number of unique characters. Because you don't know which characters will eventually reach k, a simple left/right pointer approach fails. Another common error in the Divide and Conquer approach is using indexOf to find the first invalid character but failing to split by all invalid characters or failing to process the string segment after the final invalid character.

Interview preparation tip

When studying the Longest Substring with At Least K Repeating Characters interview pattern, memorize the "poison character" concept. If a global condition requires a minimum frequency, any element falling short of that frequency globally is a guaranteed boundary. Splitting arrays or strings based on these impossible elements is a powerful Divide and Conquer technique.