Longest Substring With Exactly K Distinct Characters

Medium Strings

Given a string s and an integer k, return the length of the longest substring
of s that contains exactly k distinct characters. If no such substring exists,
return 0.
- Input: a string s and an integer k.
- Output: a single integer length.
- Constraints: 1 <= |s| <= 10^4, s holds lowercase English letters, and
0 <= k <= 26.
- Edge cases: k = 0 (always 0), k larger than the alphabet used by s (0), all
identical characters with k = 1 (|s|), and windows that shrink below k
distinct characters.
- Checking every substring with a set costs O(n^2); a frequency map that
shrinks while the window holds more than k distinct characters gives O(n).

Input Format

Line 1: s, a single line of text Line 2: k, a single integer

Output Format

Print a single integer.

Constraints

1 <= |s| <= 10^4, s holds lowercase English letters, and

Hints

Hint 1: Keep a frequency map of the current window and shrink from the

Hint 2: The window right after shrinking is the longest one ending at

Hint 3: Only windows with exactly k distinct characters are candidates, so

Examples

Example 1:

Input

eceba
2

Output

Example 2:

Input

aa
1

Output

Code runs on a free external sandbox (wandbox). Nothing executes on Scriptly's shared host.

Community solutions

Title

Language

Approach / explanation

Code

Fastest accepted solutions

Code wandbox sandbox

Ready

Compiling & running on the sandbox

Run your solution with the sample test cases to see results here.