Longest Substring with K Distinct Characters

You are provided with a string S of length N, consisting of lowercase English alphabet letters, and a positive integer K.

Your task is to determine the maximum length of a substring of S that contains at most K distinct characters.

Example:

Input:

S = "bacda"
K = 3

Output:

4

Explanation:

The substrings that have at most 3 distinct characters include: "bac", "acd", "acda". The longest one is "acda" with a length of 4, hence the result is 4.

Constraints:

• 1 <= T <= 10
• 1 <= K <= 26
• 1 <= N <= 10^4
• All characters in the string are lowercase English alphabet letters.
• Time Limit: 1 sec