Pattern visualizer
Longest K Unique Characters Substring
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. Animated on: s = "aabacbebe", k = 3 — the longest substring containing at most k distinct characters..
Grow right, shrink left only while more than k letters are in play
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.
1FUNCTION longestKUnique(s, k):2 l <- 03 best <- 04 FOR r <- 0 TO LENGTH(s) - 1:5 count[s[r]] <- count[s[r]] + 16 WHILE SIZE(count) > k:7 count[s[l]] <- count[s[l]] - 18 IF count[s[l]] = 0:9 REMOVE s[l] FROM count10 l <- l + 111 best <- MAX(best, r - l + 1)12 RETURN best
← / → step · space play · Home restart