Character Query

Moderate
0/80
10 upvotes
Asked in company
ShareChat

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 1
a b d b e
S
b
2
6 2
a e e f g l
L S
f  e
1 1
Sample Output 1:
4
6 2
Explanation of sample input 1:
For the first test case,

For the first query, the smallest index is 4, for which exactly 2 repetitions of ‘b’ is between 1 to 4. Hence, the answer is 4. 

For the second test case:

 For the first query, the largest index is 6, for which exactly 1 repetition of ‘f’ is between 1 to 6. Hence, the answer is 6.
 For the second query, the smallest index is 2, for which exactly 1 repetition of ‘e’ is between 1 to 2. Hence, the answer is 2.
Sample Input 2:
2
6 1
a c d c c a 
S 
c 
2 
6 2
d c a d c c 
S L 
c d 
1 1
Sample Output 2:
4
2 3
Hint

Try to iterate through the list for each query and find the required index.

Approaches (2)
Brute Force

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’.
Time Complexity

O( N*Q), where ‘N’ is the size of array ‘ARR’ and ‘Q’ is the number of queries.

 

In this approach, for each query, we are traversing all ‘N’ letters in the worst case. So the number of operations in the worst case is  N*Q. Hence, the overall time complexity is O(N*Q).

Space Complexity

In this approach, ignoring the space used to store the ‘ANS’ array, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Character Query
Full screen
Console