Longest Substring with At Most K Distinct Characters

Medium
786.

Longest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Paytm interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var lengthOfLongestSubstringKDistinct = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Substring with At Most K Distinct Characters Solution

Longest Substring with At Most K Distinct Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Substring with At Most K Distinct Characters is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Paytm interviews.

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.

Hints for Longest Substring with At Most K Distinct Characters

  1. Hint 1

    Same window as the two-distinct version, with the bound taken as a parameter.

  2. Hint 2

    k = 0 admits only the empty substring — answer 0.

  3. Hint 3

    Keep a tally and a distinct counter so each step is constant time.

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

  1. Handle k = 0 up front by returning 0.
  2. Add s[r] to the tally, raising the distinct count when it enters.
  3. While the distinct count exceeds k, remove s[l] and advance l.
  4. 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

Java

public static int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (k == 0) return 0;
    int[] cnt = new int[128];
    int distinct = 0, l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        if (cnt[s.charAt(r)]++ == 0) distinct++;
        while (distinct > k) {
            if (--cnt[s.charAt(l)] == 0) distinct--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

C++

int lengthOfLongestSubstringKDistinct(string s, int k) {
    if (k == 0) return 0;
    vector<int> cnt(128, 0);
    int distinct = 0, l = 0, best = 0;
    for (int r = 0; r < (int) s.size(); r++) {
        if (cnt[(int) s[r]]++ == 0) distinct++;
        while (distinct > k) {
            if (--cnt[(int) s[l]] == 0) distinct--;
            l++;
        }
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets