Skills101
← All coding problems

Longest Substring with at Most K Distinct Characters

mediumStrings II+20 XPTime limit 2s

A fruit stall records the fruits it sells through the day as a string of letters. Find the length of the longest stretch (a contiguous substring) that contains at most k different letters. In eceba with k = 2, the longest such stretch is ece — length 3.

Input:

  • line 1: the string (lowercase letters)
  • line 2: k

Output: the length of the longest substring with at most k distinct characters.

Constraints: 1 ≤ length ≤ 10⁵, 1 ≤ k ≤ 26.

Think about it: sliding window. Extend the right end one character at a time and count characters inside the window. When the window has more than k distinct characters, move the left end forward (decreasing counts, dropping letters that reach 0) until it is valid again. Record the best window size.

Sample input 1

eceba
2

Sample output 1

3

Sample input 2

aa
1

Sample output 2

2

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.