Longest Substring with At Most K Distinct Characters

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

Examples

Input	Output	Why
`s = "eceba", k = 2`	`3`	"ece".
`s = "aa", k = 1`	`2`
`s = "abc", k = 0`	`0`	No non-empty substring has zero distinct characters.

Constraints

0 ≤ |s| ≤ 5 × 10⁴
0 ≤ k ≤ 50

Hints

Hint 1

If a substring has at most k distinct letters, so does every substring inside it. That is what makes a window work.

Hint 2

Keep a count for each letter in the window. The number of keys is the number of distinct letters.

Hint 3

Extend the right end. While there are more than k keys, remove the left letter, deleting its key when the count reaches 0.

Where people lose marks

Shrinking with if instead of while: one removal may not bring the count of keys down.
Leaving zero counts in the map, so its size never falls.
k = 0: the loop shrinks every window to empty, and the answer is 0.

Dry run on `"abaccc",2`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 6

Step 1 / 6

s
a0lo/hib1a2c3c4c5
countsa×1best1
'a' enters; the window has 1 distinct letter. New longest: 1.
Step 2 / 6

s
a0lob1hia2c3c4c5
countsa×1 b×1best2
'b' enters; the window has 2 distinct letters. New longest: 2.
Step 3 / 6

s
a0lob1a2hic3c4c5
countsa×2 b×1best3
'a' enters; the window has 2 distinct letters. New longest: 3.
Step 4 / 6

s
a0b1a2loc3hic4c5
countsa×1 c×1best3
'c' enters; the window has 3 distinct letters. That is more than 2, so drop 'a', 'b' from the left until one letter disappears.
Step 5 / 6

s
a0b1a2loc3c4hic5
countsa×1 c×2best3
'c' enters; the window has 2 distinct letters.
Step 6 / 6

s
a0b1a2loc3c4c5hi
countsa×1 c×3best4
'c' enters; the window has 2 distinct letters. New longest: 4.

How to think about it

The property "at most k distinct letters" survives shrinking: remove letters from either end of a valid substring and it stays valid. So for each right end hi, the valid left ends form a contiguous block ending at hi, and the best one is the furthest left. As hi moves right, that furthest-left valid start can only move right too. That monotonicity is the whole justification for the window: lo never needs to move back.

The state is a map from letter to count. Adding s[hi] may create a (k + 1)-th key; then remove letters from the left until a key disappears. After the repair the window is the longest valid one ending at hi, and its length is a candidate for the answer.

Complexity. Time O(n) · Space O(k)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

from collections import defaultdict

def longest_k_distinct(s, k):
    count = defaultdict(int)          # letter -> copies inside the window
    best = lo = 0
    for hi, c in enumerate(s):
        count[c] += 1
        while len(count) > k:         # too many kinds: shrink from the left
            count[s[lo]] -= 1
            if count[s[lo]] == 0:
                del count[s[lo]]
            lo += 1
        best = max(best, hi - lo + 1)
    return best

#include <string>
#include <array>
#include <algorithm>

int solve(const std::string& s, int k) {
    std::array<int, 256> count{};                 // letter -> copies inside the window
    int kinds = 0, best = 0, lo = 0;
    for (int hi = 0; hi < (int)s.size(); ++hi) {
        if (count[(unsigned char)s[hi]]++ == 0) ++kinds;
        while (kinds > k) {                       // too many kinds: shrink from the left
            if (--count[(unsigned char)s[lo]] == 0) --kinds;
            ++lo;
        }
        best = std::max(best, hi - lo + 1);
    }
    return best;
}

class Solution {
    public int longestKDistinct(String s, int k) {
        int[] count = new int[256];                  // letter -> copies inside the window
        int kinds = 0, best = 0, lo = 0;
        for (int hi = 0; hi < s.length(); hi++) {
            if (count[s.charAt(hi)]++ == 0) kinds++;
            while (kinds > k) {                      // too many kinds: shrink from the left
                if (--count[s.charAt(lo)] == 0) kinds--;
                lo++;
            }
            best = Math.max(best, hi - lo + 1);
        }
        return best;
    }
}

function longestKDistinct(s, k) {
  const count = new Map();             // letter -> copies inside the window
  let best = 0, lo = 0;
  for (let hi = 0; hi < s.length; hi++) {
    count.set(s[hi], (count.get(s[hi]) || 0) + 1);
    while (count.size > k) {           // too many kinds: shrink from the left
      const n = count.get(s[lo]) - 1;
      if (n === 0) count.delete(s[lo]); else count.set(s[lo], n);
      lo++;
    }
    best = Math.max(best, hi - lo + 1);
  }
  return best;
}

fn solve(s: &str, k: usize) -> usize {
    let b = s.as_bytes();
    let mut count = [0usize; 256];                   // letter -> copies inside the window
    let (mut kinds, mut best, mut lo) = (0usize, 0usize, 0usize);
    for hi in 0..b.len() {
        if count[b[hi] as usize] == 0 { kinds += 1; }
        count[b[hi] as usize] += 1;
        while kinds > k {                            // too many kinds: shrink from the left
            count[b[lo] as usize] -= 1;
            if count[b[lo] as usize] == 0 { kinds -= 1; }
            lo += 1;
        }
        best = best.max(hi + 1 - lo);
    }
    best
}

import qualified Data.Map.Strict as M

-- The window is the original string from its left end (so shrinking is dropping the head), its length and its counts.
solve :: String -> Int -> Int
solve s k = go s s 0 M.empty 0
  where
    go [] _ _ _ best = best
    go (c:rest) win len m best =
      let m1 = M.insertWith (+) c 1 m
          (win', len', m') = shrink win (len + 1) m1
      in go rest win' len' m' (max best len')
    shrink win len m
      | M.size m <= k = (win, len, m)
      | otherwise = case win of
          (x:xs) -> shrink xs (len - 1) (M.update (\n -> if n == 1 then Nothing else Just (n - 1)) x m)
          [] -> ([], 0, m)

Variants to try

Exactly k distinct: the longest is no longer monotone in the same way; check the count of keys before recording.
Count the substrings with at most k distinct letters instead: add hi − lo + 1 at each step.

Next problems

Easy12 min

Longest run with at most k distinct letters

Examples

Constraints

Hints

Where people lose marks

Dry run on `"abaccc",2`

How to think about it

The solution, in six languages

Variants to try

Next problems

Longest run of tasks within a time budget

Longest run of distinct characters

Longest run of ones after k flips

Keep going

Longest run of tasks within a time budget

Longest run of distinct characters

Longest run of ones after k flips

The pattern behind it

Longest run with at most k distinct letters

Examples

Constraints

Hints

Where people lose marks

Dry run on "abaccc",2

How to think about it

The solution, in six languages

Variants to try

Next problems

Longest run of tasks within a time budget

Longest run of distinct characters

Longest run of ones after k flips

Keep going

Longest run of tasks within a time budget

Longest run of distinct characters

Longest run of ones after k flips

The pattern behind it

Dry run on `"abaccc",2`