Longest Substring with At Most K Distinct Characters

Medium Arrays & Hashing Sliding Window · Hash Map Original on LeetCode

Longest Substring with At Most K Distinct Characters is a medium arrays & hashing problem solved with the sliding window · hash map pattern. The best approach, optimal (sliding window with counts), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given a string s and an integer k. Return the length of the longest substring of s that contains at most k different characters.

A substring is a contiguous part of s. Characters are case-sensitive, so 'a' and 'A' count as two different characters.

Examples

Example 1

Input: s = "cbbcad", k = 2
Output: 4
Why: "cbbc" uses only b and c. Adding the next letter a would make three distinct letters.

Example 2

Input: s = "mmmm", k = 1
Output: 4
Why: The whole string has one distinct letter.

Example 3

Input: s = "xyz", k = 0
Output: 0
Why: With zero distinct letters allowed, only the empty substring qualifies.

Constraints

1 <= s.length <= 5 * 10^4
0 <= k <= 50
s consists of ASCII letters and digits.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force	`O(n²)`	`O(k)`
Optimal (sliding window with counts)	`O(n)`	`O(1)`

1Brute force

TimeO(n²)Up to n starts, each extending up to n characters.

SpaceO(k)The set holds at most k + 1 characters.

Try every start index and extend the end while counting distinct characters with a set. Stop as soon as the set grows past k; the longest stretch from any start is the answer.

For each start i, create an empty set.
For j = i, i + 1, …: add s[j]; if the set now has more than k characters, stop.
Otherwise update best with j - i + 1.

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length();
        int best = 0;
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                seen.add(s.charAt(j));
                if (seen.size() > k) break;
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        best = 0
        for i in range(n):
            seen = set()
            for j in range(i, n):
                seen.add(s[j])
                if len(seen) > k:
                    break
                best = max(best, j - i + 1)
        return best

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int n = s.size();
        int best = 0;
        for (int i = 0; i < n; i++) {
            unordered_set<char> seen;
            for (int j = i; j < n; j++) {
                seen.insert(s[j]);
                if ((int)seen.size() > k) break;
                best = max(best, j - i + 1);
            }
        }
        return best;
    }
};

function lengthOfLongestSubstringKDistinct(s, k) {
    const n = s.length;
    let best = 0;
    for (let i = 0; i < n; i++) {
        const seen = new Set();
        for (let j = i; j < n; j++) {
            seen.add(s[j]);
            if (seen.size > k) break;
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

2Optimal (sliding window with counts)

TimeO(n)Each index enters the window once and leaves at most once.

SpaceO(1)A fixed table of 128 counts.

Keep a window [l, r] with a count per character and the number of distinct characters inside. Add s[r]; if that pushes the distinct total above k, remove characters from the left until a count drops to zero and the total is back to k. Every valid window ending at r is then as long as possible.

Keep count[128], distinct = 0, l = 0.
For each r: if count[s[r]] was 0, distinct++; then count[s[r]]++.
While distinct > k: count[s[l]]--; if it became 0, distinct--; l++.
Update best with r - l + 1.

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

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        count = {}
        l = best = 0
        for r, c in enumerate(s):
            count[c] = count.get(c, 0) + 1
            while len(count) > k:
                left = s[l]
                count[left] -= 1
                if count[left] == 0:
                    del count[left]
                l += 1
            best = max(best, r - l + 1)
        return best

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        vector<int> count(128, 0);
        int distinct = 0, l = 0, best = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            if (count[(unsigned char)s[r]]++ == 0) distinct++;
            while (distinct > k) {
                if (--count[(unsigned char)s[l]] == 0) distinct--;
                l++;
            }
            best = max(best, r - l + 1);
        }
        return best;
    }
};

function lengthOfLongestSubstringKDistinct(s, k) {
    const count = new Array(128).fill(0);
    let distinct = 0, l = 0, best = 0;
    for (let r = 0; r < s.length; r++) {
        if (count[s.charCodeAt(r)]++ === 0) distinct++;
        while (distinct > k) {
            if (--count[s.charCodeAt(l)] === 0) distinct--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Edge cases to test

k = 0: the answer is 0
k at least the number of distinct characters in s: the answer is the whole length
A single character
The best window is at the very end of the string
Upper and lower case letters are different characters

Hints

Hint 1

For a fixed start, how far can the window stretch before a (k + 1)-th distinct character shows up?

Hint 2

Keep a window and a count for each character inside it. When the number of distinct characters goes over k, what should move?

Hint 3

Shrink from the left, decreasing counts, until some count hits 0 and the distinct total drops back to k.

FAQ

What is the best time complexity for Longest Substring with At Most K Distinct Characters?

Optimal (sliding window with counts) runs in O(n) time and O(1) extra space. Each index enters the window once and leaves at most once.

Which pattern does Longest Substring with At Most K Distinct Characters use?

It is a arrays & hashing problem that uses the sliding window · hash map pattern. Other problems with the same pattern: Number of Substrings Containing All Three Characters, Minimum Window Substring.

Is there a brute force solution for Longest Substring with At Most K Distinct Characters?

Yes. Brute force takes O(n²) time and O(k) space. Try every start index and extend the end while counting distinct characters with a set.

Which edge cases should I test for Longest Substring with At Most K Distinct Characters?

k = 0: the answer is 0; k at least the number of distinct characters in s: the answer is the whole length; A single character; The best window is at the very end of the string; Upper and lower case letters are different characters.