MediumHash TableStringSliding WindowUpdated Sep 2026

340. Longest Substring with At Most K Distinct Characters

Asked at TikTok

Difficulty

Medium

Time

O(n)

Space

O(k)

Pattern

Hash Table

Companies

1

Problem

You are given a string s and an integer k. Find the length of the longest substring of s that contains at most k different characters.

A substring is a block of characters that sit next to each other in the original string. You may not skip characters. "Different characters" means distinct letters — if a letter appears many times, it still counts as only one distinct character.

Return the length (a number), not the substring itself. If k is 0, no character is allowed, so the answer is 0.

Find the longest block with at most k distinct letters

s2 distinct, length 3eceba01234The window "ece" has exactly 2 distinct characters, soit is valid.s3 distinct — too manyeceba01234Adding 'b' makes 3 distinct characters, which breaksthe k = 2 limit.
With k = 2, the best block in "eceba" is "ece" — it uses only 'e' and 'c' and has length 3.

Constraints

  • ●1 <= s.length <= 5 * 10^4
  • ●0 <= k <= 50
  • ●s consists of characters from a limited alphabet

Examples

Example 1
Inputs = "eceba", k = 2
Output3
WhyThe substring "ece" uses only the two distinct characters 'e' and 'c', so its length is 3. Any longer block, like "eceb", would need 3 distinct characters, which is more than k = 2.
Example 2
Inputs = "aa", k = 1
Output2
WhyThe whole string "aa" has only one distinct character, 'a', which is within the limit k = 1. So the answer is the full length 2.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Brute force checks every substring and counts its distinct characters: O(n²) or worse.

2

Key insight: if a window has too many distinct characters, every larger window that contains it also does. So when the constraint breaks, you can safely move the left edge forward instead of restarting.

3

Keep a hash map of character counts inside the window [left, right]. Add s[right]; while the map has more than k keys, decrement s[left] (deleting it at zero) and move left right.

4

After fixing the window, right - left + 1 is a valid length — track the maximum.

5

Walkthrough for "eceba", k = 2: e,ec,ece (len 3) -> add b: 3 distinct, shrink until "eb" -> add a: shrink to "ba". Answer 3.

Optimal Approach

Step 1: count = {}, left = 0, best = 0.
Step 2: For each right:
count[s[right]] += 1
While len(count) > k:
count[s[left]] -= 1; delete it if it hits 0; left += 1.
best = max(best, right - left + 1).
Step 3: Return best.

Each character enters and leaves the window at most once.

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

Sliding window with a character count map

swindow = 3eceba01234leftrightStep 1 — right reaches index 2. The window "ece" has 2distinct characters, so it is valid.swindow = 3eceba01234leftrightStep 2 — right adds 'b' (3 distinct). Shrink leftuntil only 2 distinct remain: "ceb".swindow = 2eceba01234leftrightStep 3 — right adds 'a' (3 distinct). Shrink again to"ba". The best length seen stays 3.count[ch] += 1 when right moveswhile len(count) > k: drop s[left], left += 1best = max(best, right - left + 1)
Grow the window with right, and shrink it from the left only when the number of distinct characters goes over k.
ComplexityTime O(n)Space O(k)Each character is added to the window once and removed at most once, and the hash map holds at most k+1 distinct characters at any time.

What Trips People Up in Real Interviews

1

Not deleting keys whose count drops to zero. Then len(count) overstates the distinct characters and the window shrinks too much.

2

Restarting the window from scratch when the constraint breaks. That makes it quadratic; only move left forward.

3

Forgetting k = 0, where the answer is 0.

4

Using an if instead of a while to shrink. One removal may not be enough to get back to k distinct characters.

Solution Code

O(n) time
def lengthOfLongestSubstringKDistinct(s, k):
    count = {}
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > k:
            c = s[left]
            count[c] -= 1
            if count[c] == 0:
                del count[c]
            left += 1
        best = max(best, right - left + 1)
    return best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Longest Substring with At Most K Distinct Characters problem?

Longest Substring with At Most K Distinct Characters asks for the length of the longest substring that contains no more than `k` different characters. It is the canonical variable-size sliding window problem: grow the window greedily and shrink it only when a constraint breaks.

How do you solve Longest Substring with At Most K Distinct Characters?

The optimal approach runs in O(n) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Longest Substring with At Most K Distinct Characters?

Longest Substring with At Most K Distinct Characters is asked at TikTok. It is a medium difficulty problem.

What are common mistakes on Longest Substring with At Most K Distinct Characters?
  • Not deleting keys whose count drops to zero. Then `len(count)` overstates the distinct characters and the window shrinks too much.
  • Restarting the window from scratch when the constraint breaks. That makes it quadratic; only move `left` forward.
  • Forgetting `k = 0`, where the answer is 0.
  • Using an `if` instead of a `while` to shrink. One removal may not be enough to get back to `k` distinct characters.