Longest Substring With At Least K Repeating Characters — Medium Problem & Solution

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

Difficulty: Medium
Topics: Strings, Sliding Window, Divide and Conquer
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

If no such substring exists, return 0.

Example 1

Input: s = "aaabb", k = 3
Output: 3
Explanation: "aaa" is the longest — b appears only twice.

Example 2

Input: s = "ababbc", k = 2
Output: 5
Explanation: "ababb" has a three times and b twice.

Example 3

Input: s = "codekairo", k = 2
Output: 0
Explanation: Only o repeats, and never with anything else around it.

Constraints

1 <= s.length <= 10000
1 <= k <= 100000
s consists of lowercase English letters.

How to solve Longest Substring With At Least K Repeating Characters

The condition is not monotone, so a single sliding window fails. Adding a constraint fixes it: for a fixed number t of distinct characters, 'at most t distinct' is monotone, so a window can be maintained. Trying t = 1 .. 26 covers every possible answer.

Approach

For each t from 1 to 26, run a sliding window over s.
Track per-character counts, unique (distinct characters in the window) and atLeastK (how many of them reach k).
Shrink from the left while unique > t.
Whenever unique == t and atLeastK == t, every character in the window qualifies — record the window length.

Why it works

Any optimal substring has some number of distinct characters t* between 1 and 26; on the pass with t = t* the window can grow to exactly that substring, because the shrink rule only triggers when the distinct count exceeds t*. So the maximum over all 26 passes is the true answer.

Complexity

Time — O(26 · n)
Space — O(26)

Pitfalls

A single unconstrained window is the classic wrong answer — growing it can break the condition and shrinking it can fix it, so neither pointer moves monotonically.
Recording the window when atLeastK == t but unique < t counts a window that has not yet reached the target distinct count.
The divide-and-conquer solution — split on any character with fewer than k occurrences and recurse — is the other standard route.

Reference solution

Python

def longestSubstring(s: str, k: int) -> int:
    n = len(s)
    best = 0
    for target in range(1, 27):
        count = [0] * 26
        left = unique = at_least_k = 0
        for right in range(n):
            c = ord(s[right]) - 97
            if count[c] == 0:
                unique += 1
            count[c] += 1
            if count[c] == k:
                at_least_k += 1
            while unique > target:
                d = ord(s[left]) - 97
                if count[d] == k:
                    at_least_k -= 1
                count[d] -= 1
                if count[d] == 0:
                    unique -= 1
                left += 1
            if unique == target and at_least_k == target:
                best = max(best, right - left + 1)
    return best

JavaScript

var longestSubstring = function(s, k) {
    var n = s.length, best = 0;
    for (var target = 1; target <= 26; target++) {
        var count = [];
        for (var t = 0; t < 26; t++) count.push(0);
        var left = 0, unique = 0, atLeastK = 0;
        for (var right = 0; right < n; right++) {
            var c = s.charCodeAt(right) - 97;
            if (count[c] === 0) unique++;
            count[c]++;
            if (count[c] === k) atLeastK++;
            while (unique > target) {
                var d = s.charCodeAt(left) - 97;
                if (count[d] === k) atLeastK--;
                count[d]--;
                if (count[d] === 0) unique--;
                left++;
            }
            if (unique === target && atLeastK === target && right - left + 1 > best) best = right - left + 1;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue