Longest Substring with K Distinct Characters

You are given a string \(s\) and a list of queries. Each query is an integer \(k\). For each query, your task is to find the length of the longest substring of \(s\) that contains at most \(k\) distinct characters.

Explanation:

• Consider a substring \(s[l \ldots r]\). It satisfies the condition if the number of distinct characters in it is \(\leq k\).
• You can use the sliding window technique to efficiently find the required substring length.

Mathematically, if you denote the length of substring by \(L\) and its distinct characters count by \(|\{s[l], s[l+1], \dots, s[r]\}|\), then the condition is \( |\{s[l], s[l+1], \dots, s[r]\}| \leq k \). Your goal is to maximize \(L = r-l+1\) under this constraint.

inputFormat

The input is read from stdin and consists of:

1. A string \(s\) (without spaces).
2. An integer \(n\) representing the number of queries.
3. \(n\) space-separated integers, each denoting a value of \(k\).

outputFormat

Output a single line to stdout containing \(n\) space-separated integers. Each integer is the length of the longest substring with at most \(k\) distinct characters corresponding to each query.

abcba
2
2 3

3 5