Topics › Sliding Window and Two Pointers › Hard Problems

Longest Substring With At Most K Distinct Characters

Hard TUF ID 928 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given a string s and an integer k, return the length of the longest substring (contiguous block) of s that contains at most k distinct characters.

Constraints: 1 ≤ |s| ≤ 5 × 10^4, 0 ≤ k ≤ 50. Characters are ASCII, so a 256-entry count array covers them all.

Example 1

s = "eceba", k = 2
answer = 3          // "ece" uses only 'e' and 'c'

Example 2

s = "aaabbccd", k = 2
answer = 5          // "aaabb"; "bbcc" has length 4, "ccd" has length 3

Example 3

s = "abc", k = 0
answer = 0          // any non-empty substring has at least one distinct character

Approach 1: Brute force

Intuition. Fix the start i, extend the end j, and keep a count for each character in s[i..j]. When a character’s count goes from 0 to 1, a new distinct character has entered, so distinct increases. Once distinct > k, every longer substring from the same start also has more than k distinct characters, so we break.

The idiom freq[c]++ == 0 reads the old count, compares it with zero, then increments it. It is a compact way to say “this is the first copy of c”.

Algorithm.

1. For each i: reset freq and distinct.
2. For j = i ..: count s[j]; if it was new, increment distinct. If distinct > k, break; otherwise update best.
3. Return best.

static int bruteForce(String s, int k) {
    int n = s.length(), best = 0;
    for (int i = 0; i < n; i++) {
        int[] freq = new int[256];
        int distinct = 0;
        for (int j = i; j < n; j++) {
            if (freq[s.charAt(j)]++ == 0) distinct++;     // first copy of this character
            if (distinct > k) break;
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2) when k is large enough that the inner loop rarely breaks (plus a 256-entry reset per start). Space O(1): the table size does not depend on n.

Approach 2: Better, shrinking sliding window

Intuition. “At most k distinct characters” is monotonic: a sub-window of a valid window is valid, and a super-window of an invalid window is invalid. That is exactly what a two-pointer window needs. Grow r. When a new character pushes distinct above k, move l right, decrementing counts, until some character’s count drops to 0 and distinct is back to k. At that moment s[l..r] is the longest valid substring ending at r.

Why longest? l only moves when the window is invalid, and moving it back to the left would re-include a character we just had to drop.

Algorithm.

1. l = 0, distinct = 0, best = 0, freq[256].
2. For each r: add s[r].
3. While distinct > k: remove s[l] (decrement distinct if its count hits 0), l++.
4. Update best with r - l + 1.

static int better(String s, int k) {
    int[] freq = new int[256];
    int l = 0, distinct = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        if (freq[s.charAt(r)]++ == 0) distinct++;
        while (distinct > k) {
            if (--freq[s.charAt(l)] == 0) distinct--;     // last copy of s[l] left the window
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Complexity. Time O(2n): r and l each cross the string once. Space O(1).

Approach 3: Optimal, the window that never shrinks

Intuition. Since we only report the maximum length, a window shorter than the best one found so far is useless. So when the window becomes invalid, we move l exactly one step: the window slides right at its current length instead of shrinking. While it is invalid, we do not record it. If a longer valid substring exists, the sliding window will eventually sit on its right end with a valid content and grow by one.

This replaces the inner while with an if, so each step of r does constant work. It is the same trick as in Max Consecutive Ones III and Fruit Into Baskets; this problem is in fact Fruit Into Baskets with 2 replaced by k.

Algorithm.

1. Same state as Approach 2.
2. For each r: add s[r].
3. If distinct > k: remove s[l] once and l++.
4. If distinct <= k: update best with r - l + 1.

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

Dry run on s = "eceba", k = 2:

The window never becomes valid at length 4, so the answer stays 3.

Complexity. Time O(n): constant work per character. Space O(1): a fixed-size table.

Edge cases and pitfalls

• k = 0. No non-empty substring qualifies, so the answer is 0. All three methods handle it: the brute force breaks immediately, and the windows shrink (or slide) to empty.
• k at least the number of distinct characters. The whole string qualifies; "abcabc" with k = 3 gives 6.
• Empty string. Returns 0.
• Counting distinct correctly. Decrement distinct only when a count reaches 0, not every time a character leaves; the window may still hold other copies.
• Returning the substring itself. Some versions ask for the substring, not its length. Remember l whenever best improves (in Approach 2 the window at that moment is valid) and call substring once at the end, instead of building a new string on every improvement.
• The increment idiom. freq[c]++ == 0 compares the old value, while ++freq[c] == 1 compares the new one. Mixing the two forms between the add and remove steps is a classic off-by-one.
• Character range. The int[256] table assumes extended ASCII. For arbitrary Unicode, use a HashMap<Character, Integer> and map.size() as the distinct count.

Related problems

• Fruit Into Baskets is the special case k = 2 on integer types.
• Subarrays with K Different Integers counts windows with exactly k distinct values using this window as a subroutine.
• Count Number of Substrings counts substrings with exactly k distinct characters.
• Longest Substring Without Repeating Characters limits each character to one copy instead of limiting the number of different characters.