045. Longest Substring with At Most K Distinct

Bridge · Download this solution · All solutions and shared helpers

Problem

Return the longest substring length containing at most k distinct characters. k may be zero; nonpositive k returns zero. Repeated occurrences of the same character count as one distinct character. The empty string returns zero.

Examples

Example 1

longest_k_distinct("eceba", 2)
=> 3

The prefix ece uses two distinct characters.

Example 2

longest_k_distinct("aaa", 0)
=> 0

No nonempty window can use zero distinct characters.

Example 3

longest_k_distinct("", 3)
=> 0

Empty input has length zero.

Reveal the worked solution and reasoning

Why this mechanism works

A frequency map represents the current window, not all history. Inserting a new character may violate the distinct-count limit. Remove characters from the left until the map contains at most k keys, deleting keys whose counts reach zero.

State and boundaries

counts contains exactly positive frequencies in the active window. left is repaired before best is updated.

Protocol

Add the incoming character.
While the distinct count exceeds k, consume the left character.
Delete a count that becomes zero.
Advance left.
Commit the longest valid window ending here.

Visualization

e c e b a, k=2
[e c e] valid length 3
add b -> shrink until only e,b remain

Python implementation

def longest_k_distinct(text, k):
    if k <= 0:
        return 0
    counts = {}
    left = best = 0
    for right, char in enumerate(text):
        counts[char] = counts.get(char, 0) + 1
        while len(counts) > k:
            old = text[left]
            counts[old] -= 1
            if counts[old] == 0:
                del counts[old]
            left += 1
        best = max(best, right - left + 1)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

longest_k_distinct("eceba", 2)

L2 longest_k_distinct: if k <= 0:
text='eceba'; k=2

L4 longest_k_distinct: counts = {}
text='eceba'; k=2; counts={}

L5 longest_k_distinct: left = best = 0
text='eceba'; k=2; counts={}; left=0; best=0

L6 longest_k_distinct: for right, char in enumerate(text):
text='eceba'; k=2; counts={}; left=0; best=0; right=0; char='e'

L7 longest_k_distinct: counts[char] = counts.get(char, 0) + 1
text='eceba'; k=2; counts={'e':1}; left=0; best=0; right=0; char='e'

L14 longest_k_distinct: best = max(best, right - left + 1)
text='eceba'; k=2; counts={'e':1}; left=0; best=1; right=0; char='e'

L6 longest_k_distinct: for right, char in enumerate(text):
text='eceba'; k=2; counts={'e':1}; left=0; best=1; right=1; char='c'

L7 longest_k_distinct: counts[char] = counts.get(char, 0) + 1
text='eceba'; k=2; counts={'e':1, 'c':1}; left=0; best=1; right=1; char='c'

... 15 intermediate state changes omitted ...

L9 longest_k_distinct: old = text[left]
text='eceba'; k=2; counts={'e':1, 'b':1, 'a':1}; left=2; best=3; right=4; char='a'; old='e'

L10 longest_k_distinct: counts[old] -= 1
text='eceba'; k=2; counts={'e':0, 'b':1, 'a':1}; left=2; best=3; right=4; char='a'; old='e'

L12 longest_k_distinct: del counts[old]
text='eceba'; k=2; counts={'b':1, 'a':1}; left=2; best=3; right=4; char='a'; old='e'

L13 longest_k_distinct: left += 1
text='eceba'; k=2; counts={'b':1, 'a':1}; left=3; best=3; right=4; char='a'; old='e'

Result: 3. The prefix ece uses two distinct characters.

longest_k_distinct("aaa", 0)

L2 longest_k_distinct: if k <= 0:
text='aaa'; k=0

Result: 0. No nonempty window can use zero distinct characters.

Why the solution is correct

Insertion is the only way validity can break. Removing a left prefix eventually restores the key limit, and stopping at the first valid position keeps the longest valid suffix for that endpoint. The maximum over endpoints is the global optimum.

Time and space

O(n) expected time because each endpoint advances at most n times; O(min(n,u)) map space.

Common mistakes

Leaving zero-count keys inflates the distinct count. A single if repair may leave several excess occurrences before a distinct key disappears.

Reasoning card

State: counts contains exactly positive frequencies in the active window. left is repaired before best is updated.

Invariant: After repair, the map describes a valid window with at most k keys.

Decision to rehearse: Maintain counts; delete a key only when its count reaches zero.

Finish: Commit the longest valid window ending here

Transfer exercise

Compare the state needed for at most k distinct characters with at most k total occurrences of one distinguished character.