Longest Substring with At Most K Distinct Characters Queries

Given a string s of length n and q queries, each query consists of an integer k. For each query, you are required to compute the length of the longest contiguous substring of s that contains at most k distinct characters.

The task is a combination of sliding window and counting distinct characters techniques. In particular, if we denote by L the length of a substring, then we are to maximize L such that the number of distinct characters in that substring, denoted by \( \#distinct \), satisfies \( \#distinct \leq k \).

Example:

Input: s = "aabbcca", queries = [1, 2, 3]
Output: [2, 4, 7]

For k=1, the longest substring with 1 distinct character is "aa" or "bb" or "cc", so the answer is 2. Similarly, for k=2 and k=3 the answers are 4 and 7 respectively.

inputFormat

The first line contains two integers n and q separated by a space, where n is the length of the string and q is the number of queries.

The second line contains a string s of length n.

If q > 0, the third line contains q integers separated by spaces, each representing a value of k for which you must compute the desired length.

outputFormat

Output a single line containing q integers separated by a space. Each integer represents the length of the longest substring of s that contains at most the respective k distinct characters.

## sample

7 3
aabbcca
1 2 3

2 4 7