Last Updated: 20 Oct, 2021

Character Query

Moderate

Asked in company

Problem statement

Ninja has a list of letters. List ‘ARR’ consists of ‘N’ lowercase letters indexed from 1 to ‘N’ . Ninja had tried to memorize the position of these letters. To test the memorizing skills of Ninja, his friend will ask ‘Q’ questions of either of the type:

1.  L ch K: Tell the largest index IDX for which there are exactly  K repetitions of character ch between indices 1 to IDX.
2.  S ch K: Tell the smallest index IDX for which there are exactly K repetitions of character ch between indices 1 to IDX.

Can you help Ninja to answer these ‘Q’ queries?

You are given a list of ‘ARR’ containing ‘N’ letters and ‘TYPE’,’ LETTER’, ‘VALUES’ representing the data of ‘Q’ queries.TYPE[i] tells the type of ith query.LETTER[i] denotes the character, and VALUE[i] represents the number of repetitions.

For Example

If the given ‘ARR’ is [a,b,d,b,e] and the query is S b 2. Then the answer will be  4 as 4 is the smallest index for which 2 repetitions of ’b’ exist between 1 to 4.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, 'N’ and ‘Q’, denoting the number of letters and queries, respectively.

The second line contains the list of letters ‘ARR’.

The third line contains ‘TYPE’ array where TYPE[i] denotes the type of ith query.

The fourth line contains ‘LETTER’ array where LETTER[i] denotes the letter considered for ith query.

The fifth line contains ‘VALUE’ array where VALUE[i] denotes the number of repetitions for ith query.

Output Format:

For each test case, print a list of ‘Q’ values where ith value is the answer of ith query.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N,Q <= 10^4.  

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will iterate through the list for each query, count the frequency of the respective character, find the required index according to the type of query asked, and store the answers of each query in an array ‘ANS’.

At last, we will return the ‘ANS’ array.

Algorithm:

Define an array ‘ANS’ to store the answers to each query.
For i in range 0 to Q-1:
- Set ‘FREQ’ as 0.
- For j in range 0 to N-1:
  - If ‘ARR’[j] is equal to ‘LETTER[i]’:
    - Increment the ‘FREQ’.
    - Set ‘FREQ’ as ‘FREQ’+1.
  - If ‘TYPE[i]’==’S’ and ‘FREQ’ == ‘VALUE[i]’:
    - We found the smallest index.
    - Append (j+1) into ‘ANS’.
    - Break.
  - If ‘TYPE[i]’==’L’ and ‘FREQ’==’VALUE[i]’ +1:
    - We can’t include this letter. So, we will consider the list from index 1 to j.
    - Append j to ‘ANS’.
    - Break.
  - If ‘TYPE[i]’ == ‘L’ and j==’N’-1:
    - There are only ‘VALUE[i]’ repetitions of ‘LETTER[i]’ between 1 to N.
    - So, for query type ‘L’, the answer will be N.
    - Append ‘N’ to ‘ANS’.
Answer for all queries has been computed.
Return ‘ANS’.

Solve now

02 Approach

If we try to observe the answer, we found a pattern that :

For Type ‘S’, the answer is the index of the VALUE[i]’th repetition of ‘LETTER[i]’ as it is the smallest index so that exactly ‘VALUE[i]’ repetition of ‘LETTER’[i] occurs between 1 to this index.

For Type ‘L’, the answer will be one less than the index of the (VALUE[i] +1)^th occurrence of ‘LETTER[i]’.Because if we include that index, we will have more extra repetition in the range. So, the largest index possible is one less than the index of the (VALUE[i] +1)^th occurrence of ‘LETTER[i]’.

To find the indices of each character quickly, we will store the indices of all occurrences of each character in a 2-D array, ‘INDICES’. INDICES[i][j] will denotes index of j+1^th occurrence of (i+1)^th character. So, with the help of his 2-D array, we can answer each query in constant time.

Algorithm:

Declare an array of dynamic arrays of size 26 to store the indices of all occurrences of each character.
For i in range 0 to N-1:
- Append i+1 into ‘INDICES’[ARR[i] - ‘a’].
‘INDICES’ array is computed. Now, we can answer the queries.
Declare the ‘ANS’ array to store the answer to each query.
For i in range 0 to Q:
- If ‘TYPE[i]’ == ‘S’:
  - Answer is the index of the VALUE[i]’th repetition of ‘LETTER[i]’.
  - Append INDICES[ ‘LETTER[i]’ - ‘a’ ][ VALUE[i] - 1] into ‘ANS’.
- If ‘TYPE[i] == ‘L’:
  - If size of INDICES[ ‘LETTER[i]’ - ‘a’ ] is equal to VALUE[i]:
    - There exist only VALUE[i] repetitions .So the answer will be N.
    - Append ‘N’ to ‘ANS’.
  - Else:
    - The answer is one less than the index of the (VALUE[i] +1)^th occurrence of ‘LETTER[i]’.
    - Append INDICES[ ‘LETTER[i]’ - ‘a’ ][ VALUE[i] ] -1 into ‘ANS’.
Answers for all queries are computed.
Return ‘ANS’.

Solve now