# Find the index, where the given the character ch has exactly r repetitions

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

Sample Input
1
aabbabb
2
L a 2
S a 2

Sample Output
4 (indexed from 1 to N)
2

1 Like

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 )

Lookup for modified binary-search : -

1 Like