medium +18 pts

Longest Substring with K Repeating Characters

Find the longest substring where each character appears at least K times.

Share
strings sliding-window substring frequency
Given a string `s` and an integer `k`, find the length of the longest substring such that every character in that substring occurs at least `k` times. If no such substring exists, return 0. Implement the function `longest_substring(s: str, k: int) -> int`. A substring is a contiguous sequence of characters within `s`. Only non-empty substrings are considered.

Constraints

- `1 <= len(s) <= 1000` - `1 <= k <= 1000` - `s` contains only lowercase English letters. - The function should run within O(n^2) time in the worst case, with O(1) extra space (not counting the input).

Example

>>> longest_substring("aaabb", 3)
3
>>> longest_substring("ababbc", 2)
5
>>> longest_substring("aaabbb", 2)
6
>>> longest_substring("abc", 2)
0
18 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try every possible starting index and extend the substring to the right, keeping counts.
Track how many distinct characters in the current window appear fewer than k times.
Stop extending when the number of distinct characters exceeds the maximum allowed for a given window.
Remember that the maximum number of distinct characters in any valid substring is at most 26.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.