DSA problem

Longest Substring with At Least K Repeating Characters

MediumSliding Window - Dynamic SizePattern: Sliding Window with Distinct-Char Constrainttop600AmazonGoogleMicrosoftBloomberg

Given a string s and an integer k, return the length of the longest substring of s such that every character in that substring appears at least k times.

If no such substring exists, return 0.

The tricky part is that the "every character appears at least k times" condition is not monotonic, so a naive single-window scan does not work directly. The standard technique fixes the number of distinct characters allowed in the window (from 1 to 26), and for each fixed count runs a valid sliding window. For a fixed distinct count, the window grows and shrinks predictably, and you record windows where all present characters meet the frequency threshold.

Examples

Example 1

Input: s = "aaabb", k = 3

Output: 3

Explanation: The longest valid substring is "aaa", since "a" is repeated 3 times. "b" only appears twice, so it cannot be included.

Example 2

Input: s = "ababbc", k = 2

Output: 5

Explanation: The longest valid substring is "ababb", where "a" appears 2 times and "b" appears 3 times, both at least k = 2.

Example 3

Input: s = "bbaaacbd", k = 3

Output: 3

Explanation: Only "aaa" satisfies the condition, since "a" appears 3 times and no longer valid window exists.

Constraints

1 <= s.length <= 10^4
s consists of only lowercase English letters.
1 <= k <= 10^5

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowhash-tablestringdivide-and-conquer

Browse all DSA problems