Given a string S indexed from 1 to N. Given character ch and number of repetition r.
There are two types of queries
L ch r - the largest index from 1 to N where there is exactly r repetition of character ch.
S ch r - the smallest index from 1 to N where there is exactly r repetition of character ch.
An index always exists for each query.
Input Format
For each test case T.
Contains a string S and the next line contains Q the number of queries.
Followed by Q lines of queries
Make a 2d-dp-array to store the prefix sums for each character from βaβ to βzβ,
so it is : -dp[26][n];
Now, for the string : - aabbabb ;
The 2d-array looks like this : -
a : 1 1 0 0 1 0 0
b: 0 0 1 1 0 1 1
c: 0 0 0 0 0 0 0
and so
onβ¦
Now, do the prefix sum for each row and 2d-array will look like this :-
a : 1 2 2 2 3 3 3
b : 0 0 1 2 2 3 4
Now, when you receive the query for word βaβ , you should focus on first row, say , r=2; the indices having position βrβ(2) are : - β2β,β3β,β4β , so one of them is our answer ,
when largest index is asked, do modified binary search to find the index of the element in the array with value β2β(but β2β should be at the end )
Similarly, do modified binary search to find the index of the element in the array with value β2β(but β2β should be at the beginning )