Longest Substring with At Most K Distinct Characters

mediumSave

Hash TableSliding WindowStringTwo Pointers

Given a string s and an integer k, find the length of the longest substring t of s such that t contains at most k distinct characters. Your solution should return this length.

Example 1

Input

[
  "eceba",
  "2"
]

Output

Explanation. The longest substring with at most 2 distinct characters is "ece", "ceb" or "eba". All have length 3.

Example 2

Input

[
  "aaacccbbbaaa",
  "1"
]

Output

Explanation. With k=1, the longest substrings are "aaa", "ccc", "bbb", each of length 3.

Example 3

Input

[
  "abaccc",
  "2"
]

Output

Explanation. The longest substring with at most 2 distinct characters is "accc", which has 'a' and 'c' as distinct characters, and a length of 4.

Example 4

Input

[
  "abcde",
  "3"
]

Output

Explanation. The longest substrings are "abc", "bcd", "cde", each having 3 distinct characters and a length of 3.

Example 5

Input

[
  "aaaaaaa",
  "5"
]

Output

Explanation. The entire string "aaaaaaa" has only 1 distinct character ('a'). Since k=5, the entire string satisfies the condition, and its length is 7.

Example 6

Input

[
  "a",
  "1"
]

Output

Explanation. The string "a" has 1 distinct character. k=1, so the length is 1.

Example 7

Input

[
  "ab",
  "1"
]

Output

Explanation. The longest substring with at most 1 distinct character is "a" or "b", each of length 1.

Follow-up: Can you adapt your solution if the input string `s` could contain Unicode characters (beyond basic ASCII), and `k` could be very large (up to `s.length`)?

Constraints:

- `1 <= s.length <= 5 * 10^4` - `s` consists of English lowercase letters. - `1 <= k <= 26`

Views: 3