Longest Substring with At Most K…

1. Define the problem

Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, find the length of the longest substring that contains at most k distinct characters . Grow right always; shrink from the left whenever the window exceeds k distinct chars.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
0 ≤ k ≤ 50

Example

Inputs = "eceba", k = 2

Output3

Explanation The answer is "ece" with length 3.

2. Know the words first

In plain terms

Substring: A run of characters taken right out of the string as-is, next to each other in order — not letters picked out from anywhere, that's a different thing (a subsequence).

3. Visualize the solution

Keep the window within k distinct chars

StatusGrow

Window "e" — 1 distinct, best = 1.

What happens in this step

window = [0, 0]  "e"
freq = {e:1}  (size=1 <= k=2)

best = max(0, 0-0+1) = 1

Step 1 of 4

Steps to visualize

Grow right and increment the frequency of the entering character.
When the map holds more than k distinct keys, shrink left until it fits.
Delete a character from the map when its count hits zero.
After each valid step, update best with the current window length.
Continue until right reaches the end of the string.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Keep the window within k distinct chars

StatusGrow

Window "e" — 1 distinct, best = 1.

What happens in this step

window = [0, 0]  "e"
freq = {e:1}  (size=1 <= k=2)

best = max(0, 0-0+1) = 1

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function lengthOfLongestSubstringKDistinct(s, k) {
  if (k <= 0 || s.length === 0) return 0;

  const freq = new Map();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    freq.set(c, (freq.get(c) ?? 0) + 1);

    while (freq.size > k) {
      const lc = s[left];
      const n = freq.get(lc) - 1;
      if (n === 0) {
        freq.delete(lc);
      } else {
        freq.set(lc, n);
      }
      left++;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

Time: O(n)
Space: O(k)

6. Test cases

Test cases

Input	Expected	Covers
`s = "eceba", k = 2`	`3`	Docstring example
`s = "", k = 2`	`0`	Empty string
`s = "abc", k = 0`	`0`	k = 0 → no valid substring
`s = "aabbcc", k = 1`	`2`	k = 1
`s = "aab", k = 3`	`3`	Fewer distinct chars than k
`s = "abaccc", k = 10`	`6`	k >= distinct count returns full length
`s = "aaaa", k = 1`	`4`	All identical characters
`s = "a", k = 1`	`1`	Single character string
`s = "araaci", k = 2`	`4`	Classic "araa" example
`s = "abcadcacacaca", k = 3`	`11`	Larger hand-verified case
`s = "xyzzyxzxyzyzyxxzzy", k = 2`	`5`	Another larger hand-verified case

Longest Substring with At Most K Distinct Characters