Longest Substring with K Distinct Characters

Medium·Tagsstringsliding-windowhash-table

Problem Statement

Given a string, find the length of the longest substring in it with no more than `k` distinct characters. You can assume that `k` is less than or equal to the length of the given string.

Examples

Example 1

Input

k: 2, str: "araaci"

Output

"4"

Why

The run "araa" uses only two distinct letters, a and r, and is 4 characters long, the most you can cover before a third distinct letter appears.

Example 2

Input

k: 1, str: "araaci"

Output

"2"

Why

With only one distinct letter allowed, the longest run is "aa", which is 2 characters.

Example 3

Input

k: 3, str: "cbbebi"

Output

"5"

Why

Allowing three distinct letters, both "cbbeb" and "bbebi" reach 5 characters, the longest stretch possible here.

Constraints

•1 <= str.length <= 100000
•1 <= k <= str.length
•The string consists of standard ASCII characters.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

We can use a HashMap or an integer array to remember the frequency of each character we have processed.

Hint 2

Insert characters from the beginning of the string into the map until we have 'K' distinct characters.

Hint 3

These characters will constitute our sliding window. Keep expanding the window, but as soon as the distinct character count exceeds 'K', start shrinking the window from the left until you are back to 'K' distinct characters.