Longest with at most k different letters

Lesson 1.5 · Medium · Variable window · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Given a string and k, find the longest substring that has at most k different letters.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

L/Re0

d10

e11

e12

d13

b14

b15

b16

c17

a18

b19

Window has 1 different letters. Length 1.

counts {e:1} · best 1

1 / 35

The idea

Complexity

Time	Space	Why
`O(n)`	`O(k)`	Two forward-only pointers; the count map holds at most k + 1 letters.

In Python

from collections import defaultdict
def at_most_k(s, k):
    cnt, l, best = defaultdict(int), 0, 0
    for r, ch in enumerate(s):
        cnt[ch] += 1
        while len(cnt) > k:
            cnt[s[l]] -= 1
            if cnt[s[l]] == 0: del cnt[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

Try it on LeetCode: Longest Substring with At Most K Distinct Characters →

Summary: say it in the interview

A set is no longer enough, so keep counts per letter. When the number of different letters goes above k, shrink L and remove letters whose count hits zero.
Time O(n), space O(k). Two forward-only pointers; the count map holds at most k + 1 letters.