Longest Substring with K Distinct Characters in a Range

Problem Description:

Given a string ( s ), an integer ( k ) and ( Q ) queries, each query consists of two integers ( L ) and ( R ) representing the starting and ending indices (1-indexed) of a substring. For each query, you are required to compute the length of the longest substring within ( s[L, R] ) that contains no more than ( k ) distinct characters.

For example, if ( s = "abcba" ), ( k = 2 ) and one query is ( (2, 5) ), then the considered substring is "bcba" and the longest substring with at most 2 distinct characters is "bcb" with length 3.

Mathematically, for each query, compute

[ \max_{L \leq i \leq j \leq R} { j - i + 1 \mid \text{the substring } s[i\ldots j] \text{ contains at most } k \text{ distinct characters} } ]

Note: The indices in the queries are 1-indexed.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains the string ( s ).
2. The second line contains an integer ( k ) — the maximum number of distinct characters allowed.
3. The third line contains an integer ( Q ) — the number of queries.
4. Each of the next ( Q ) lines contains two space-separated integers ( L ) and ( R ), specifying the 1-indexed starting and ending positions of the substring to consider.

outputFormat

For each query, output a single integer on a new line representing the length of the longest substring (within the specified subrange) that contains at most ( k ) distinct characters. The output should be sent to standard output (stdout).## sample

abcba
2
2
1 3
2 5

2
3