Last Updated: 7 Dec, 2020
Count ROR
Easy
Asked in company
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).
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.
Approaches
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.
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’.
Since there will exist repeating sub-problems, we can hash them using a 2-D ‘dp’ array where ‘dp[i][j]’ tells the number of matches till ‘i’th index in ‘S’ and ‘j’th index in ‘T’.
The steps are as follows:
- Maintain a ‘dp’ array that stores the count of matches in ‘S’, initialized to -1.
- We will use a helper function for recurring called ‘countROR’ which takes string ‘S’,string ‘T’ which is “ROR”, integer ‘i’, and ‘j’ which denotes the position of ‘S’ and ‘T’ respectively and ‘dp’ array.
- 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 we have already visited the ‘i’, ‘j’ th position, return ‘dp[i][j]’.
- 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 and at the same time store it in ‘dp[i][j]’ .
- Return ‘countROR’ where ‘S’ is ‘S’, ‘T’ is “ROR”, ‘i’ and ‘j’ are 0, as the final answer.
To find the number of “ROR” subsequences in the given string, observe for each ‘O’ if we know a number of ‘R’ before and after it. Then the number of “ROR” subsequences for that ‘O’ is equal to the product of the number of ‘R’ before and after that ‘O’.
So, the idea is to maintain a variable to store the number of ‘R’ before index I, if the ith character of the string is ‘O’ and the number of ‘O’ before index I if the ith character is ‘R’.
The steps are as follows:
- Maintain 3 variables to maintain ‘countR’, ‘countRO’, ‘countROR’, all initialized to 0.
- Loop from 0 to length of ‘S’:
- If ‘S[i]’ is ‘O’, add ‘countR’ in ‘countRO’.
- Else, increase the ‘countR’ by 1, and add ‘countRO’ to ‘countROR’.
- Return ‘countROR’ as the final answer.
Similar problems