Longest Substring with At Most K Distinct Characters — Medium Problem & Solution

Return the length of the longest substring of s that contains at most k distinct characters.

Difficulty: Medium
Topics: Strings, Hash Table, Sliding Window
Asked at: Amazon, Google, Paytm
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

Return the length of the longest substring of s that contains at most k distinct characters.

Example 1

Input: s = "codekairo", k = 3
Output: 3
Explanation: No window of four keeps the alphabet down to three here.

Example 2

Input: s = "eceba", k = 2
Output: 3
Explanation: "ece".

Example 3

Input: s = "aa", k = 1
Output: 2

Constraints

1 <= s.length <= 100000
0 <= k <= 50
s consists of English letters.

How to solve Longest Substring with At Most K Distinct Characters

Generalise the two-distinct window: grow on the right, and while the distinct count exceeds k, shrink from the left. The tally makes each update constant time.

Approach

Handle k = 0 up front by returning 0.
Add s[r] to the tally, raising the distinct count when it enters.
While the distinct count exceeds k, remove s[l] and advance l.
Track the longest valid window.

Why it works

Shrinking a window can only lower its distinct count, so for a fixed right edge the valid left edges are a suffix — the hallmark of a two-pointer window. Every index is added and removed once, so the scan is linear regardless of k.

Complexity

Time — O(n)
Space — O(min(n, alphabet))

Pitfalls

k = 0 must not fall through into the loop, where the shrink would run past the right edge.
Forgetting to decrement the distinct count on a zero tally silently caps the window.
The answer is a length, not a count of substrings.

Reference solution

Python

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    if k == 0:
        return 0
    cnt = {}
    distinct = 0
    l = 0
    best = 0
    for r, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1
        if cnt[c] == 1:
            distinct += 1
        while distinct > k:
            u = s[l]
            cnt[u] -= 1
            if cnt[u] == 0:
                distinct -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

JavaScript

var lengthOfLongestSubstringKDistinct = function(s, k) {
    if (k === 0) return 0;
    var cnt = {};
    var distinct = 0, l = 0, best = 0;
    for (var r = 0; r < s.length; r++) {
        var c = s.charAt(r);
        cnt[c] = (cnt[c] || 0) + 1;
        if (cnt[c] === 1) distinct++;
        while (distinct > k) {
            var u = s.charAt(l);
            cnt[u]--;
            if (cnt[u] === 0) distinct--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 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