Maximum Substring Length with K Distinct Characters

You are given a string s and an integer k. Your task is to determine the maximum length of any substring of s that contains at most k distinct characters. In other words, find the length of the longest contiguous segment of the string in which the number of unique characters is no more than k.

Note: When k is 0 or the string is empty, the answer is defined to be 0.

The problem can be approached using the sliding window technique. Mathematically, if we denote by \( f(s, k) \) the maximum length of a substring of s containing at most k distinct characters, then we need to maximize the window size subject to the constraint:

[ |{ c : c \in s[i \ldots j] }| \leq k ]

inputFormat

The input is given via standard input (stdin). The first line contains an integer T indicating the number of test cases. Each test case consists of two lines. The first line of each test case contains an integer k. The second line contains the string s.

outputFormat

For each test case, output a single integer on a separate line which represents the maximum length of a substring of s that contains at most k distinct characters.## sample

3
2
abcba
3
aabbcc
1
abc

3
6
1