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

2 Likes

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 :slight_smile: )

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 :slight_smile: )

Lookup for modified binary-search : -

1 Like