Skip to main content

87. Longest Substring with At Most K Distinct Characters

mediumAsked at Workday

Find the length of the longest substring with at most k distinct characters. Workday uses this for sliding-window with constraint counters — same shape as 'longest payroll window covering at most k distinct cost centers'.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

Problem

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

Constraints

  • 1 <= s.length <= 5 * 10^4
  • 0 <= k <= 50

Examples

Example 1

Input
s = "eceba", k = 2
Output
3

Explanation: The substring is 'ece' with length 3.

Example 2

Input
s = "aa", k = 1
Output
2

Approaches

1. All substrings

Check every substring's distinct character count.

Time
O(n^3)
Space
O(k)
// nested + count — way too slow

Tradeoff: Cubic. Won't pass.

2. Sliding window with distinct-count map

Expand right, tracking char counts. When distinct > k, shrink left until <= k. Track best.

Time
O(n)
Space
O(k)
function lengthOfLongestSubstringKDistinct(s, k) {
  if (k === 0) return 0;
  const counts = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    while (counts.size > k) {
      counts.set(s[left], counts.get(s[left]) - 1);
      if (counts.get(s[left]) === 0) counts.delete(s[left]);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Tradeoff: Map.size tracks distinct chars. Single pass; each char enters and leaves the map once.

Workday-specific tips

Workday wants the canonical sliding-window. The key: delete from the map when count hits 0 (otherwise size overcounts). Walk through with 'eceba', k=2 before coding.

Common mistakes

  • Tracking distinct count separately when Map.size already does it — extra bug surface.
  • Forgetting to delete entries with count 0 — Map.size stays inflated.
  • Computing best after shrinking instead of after expansion.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • Longest Substring with At Most 2 Distinct (LC 159) — same template, k=2.
  • Fruit Into Baskets (LC 904) — same shape.
  • Longest Substring Without Repeating Characters (LC 3) — k unbounded.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why delete on count 0?

Map.size is our distinct-character counter. If we leave 0-count entries in, size overestimates distinct count.

k = 0?

Edge case. Length 0 is the only valid 'at most 0 distinct' substring. Handle upfront.

Practice these live with InterviewChamp.AI

Drill Longest Substring with At Most K Distinct Characters and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →