Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Examples

Example 1:

Input: s = "eceba", k = 2

Output: 3

Explanation: The substring "ece" has length 3 with 2 distinct characters ('e' and 'c').

Example 2:

Input: s = "aa", k = 1

Output: 2

Explanation: The entire string "aa" has only 1 distinct character, which is within the limit.

Example 3:

Input: s = "araaci", k = 2

Output: 4

Explanation: The substring "araa" has length 4 with 2 distinct characters ('a' and 'r').

Constraints

• 1 <= s.length <= 10⁵
• s consists of English letters.
• 0 <= k <= s.length