Count ROR

Easy
0/40
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in company
Samsung

Problem statement

You are given a string ‘S’, containing all capital letters from ‘A’ - ‘Z’. Your task is to count the number of times the “ROR” occurs as a subsequence in the string ‘S’.

Note: 
Since the answer can be very large print the answer modulo 10 ^ 9 + 7.

For example

Given:
‘S’ = OORROR.
The answer will be two since 2 “ROR” can be formed from the index (2,4,5), and (3,4,5) (0-based indexing).
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ line contains a string ‘S,’ containing capital letters.
Output Format : 
For each test case, You are supposed to return an integer that denotes the total number of times “ROR” occurs as a subsequence.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4

Time Limit: 1sec.

Sample Input 1 :

2
OORROR
OOROR

Sample Output 1 :

2
1

Explanation of the Sample Input 1:

In the first test case, The answer will be 2, since 2 “ROR” can be formed from the index (2,4,5), and (3,4,5) (0-based indexing).

In the second test case, The answer will be 1, since 1 “ROR” can be formed from the index (2,3,4) (0-based indexing).

Sample Input 2 :

2
ROOROO
RRROO

Sample Output 2 :

2
0
Hint

Can we naively match the strings?

 

Approaches (3)
Using Recursion

The idea is to use recursion and match “ROR” in our string ‘S’. If we match at some index, then we recur on the rest of the substring of “ROR” and ‘S’, but at the same time also recur for the same position of “ROR” in ‘S’.


 

The steps are as follows:

  • We will use a recurring helper function ‘countROR’, which takes four arguments string ‘S’, the string ‘T’ which is “ROR”, integer ‘i’, and ‘j’, which denotes the position of ‘S’ and ‘T’ respectively.
    • The base condition will be if ‘j’ is greater than the length of ‘T’, then return 1, since we found a valid combination.
    • We maintain two variables, ‘match’ and ‘noMatch’ initially 0, to maintain the count if we find a match in string ‘S’ and ‘T’, respectively.
    • If ‘S[i]’ is equal to ‘T[j]’ then recur for ‘i + 1’, ‘j + 1’ and store in ‘match’.
    • In every case, recur for ‘i + 1’, ‘j’ and store in ‘noMatch’.
    • Return the sum of ‘match’ and ‘noMatch’ as the final answer.
  • Return ‘countROR’ with arguments ‘S’ is ‘S’, ‘T’ is “ROR”, ‘i’ and ‘j’ are 0, as the final answer.
Time Complexity

O((2 ^ N)), Where ‘N’ is the length of ‘S’.


Since we are using recursion and for each case we have two calls, therefore the overall time complexity will be O(2 ^ N). 

Space Complexity

O(N), Where ‘N’ is the length of ‘S’.

Since we are using recursion, a call stack up to height ‘N’ would be made. Hence the overall space complexity will be O(N). 

Code Solution
(100% EXP penalty)
Count ROR
Full screen
Console