Longest Substring with K Uniques

Grow right, shrink left only while more than k letters are in play

time O(n)space O(k)

Checking every substring is quadratic, and almost all of that work is repeated: a window that already holds too many letters cannot be fixed by widening it further. Keep a tally of how many copies of each letter the window holds. The right edge takes in one cell per step; if that pushes the tally past k keys, the left edge walks right, decrementing as it goes and dropping a letter from the tally the moment its count hits zero. The left edge never moves backwards, so each cell is entered once and left at most once — linear time, and the tally never exceeds k + 1 keys.

Details

Animated on: s = "aabacbebe", k = 3 — the longest substring containing at most k distinct characters.

Problem:Longest Substring with K UniquesMedium

Grow right, shrink left only while more than k letters are in play

step 1 / 11

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Every substring holding at most 3 distinct letters is a window, and widening one can only ever ADD a letter while narrowing it from the left can only ever remove one. So a single window that grows on the right and gives ground on the left visits every candidate worth checking, in one pass.

Pseudocode

1FUNCTION longestKUnique(s, k):
2  l <- 0
3  best <- 0
4  FOR r <- 0 TO LENGTH(s) - 1:
5    count[s[r]] <- count[s[r]] + 1
6    WHILE SIZE(count) > k:
7      count[s[l]] <- count[s[l]] - 1
8      IF count[s[l]] = 0:
9        REMOVE s[l] FROM count
10      l <- l + 1
11    best <- MAX(best, r - l + 1)
12  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Every substring holding at most 3 distinct letters is a window, and widening one can only ever ADD a letter while narrowing it from the left can only ever remove one. So a single window that grows on the right and gives ground on the left visits every candidate worth checking, in one pass.
'a' at index 0 is a letter the window had not seen, so it pushes the distinct count up. "a" holds 1 distinct letter (a) across 1 cell — a new best.
'a' at index 1 is already inside the window, so it costs nothing — the distinct count is unchanged. "aa" holds 1 distinct letter (a) across 2 cells — a new best.
'b' at index 2 is a letter the window had not seen, so it pushes the distinct count up. "aab" holds 2 distinct letters (a, b) across 3 cells — a new best.
'a' at index 3 is already inside the window, so it costs nothing — the distinct count is unchanged. "aaba" holds 2 distinct letters (a, b) across 4 cells — a new best.
'c' at index 4 is a letter the window had not seen, so it pushes the distinct count up. "aabac" holds 3 distinct letters (a, b, c) across 5 cells — a new best.
'b' at index 5 is already inside the window, so it costs nothing — the distinct count is unchanged. "aabacb" holds 3 distinct letters (a, b, c) across 6 cells — a new best.
'e' at index 6 is a letter the window had not seen, so it pushes the distinct count up. That put 4 distinct letters in play, one too many, so the left edge walks from 0 to 4 until 'a' has no copies left and the window is legal again. "cbe" is only 3 wide against the best of 6, so the record stands.
'b' at index 7 is already inside the window, so it costs nothing — the distinct count is unchanged. "cbeb" is only 4 wide against the best of 6, so the record stands.
'e' at index 8 is already inside the window, so it costs nothing — the distinct count is unchanged. "cbebe" is only 5 wide against the best of 6, so the record stands.
Every right edge has been tried. The widest window that never held more than 3 distinct letters was "aabacb" at indices 0..5 — 6 cells over 3 letters. Return 6.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Substring with K Uniques in the editor All Sliding Window problems Back to roadmap