Last Updated: 10 Oct, 2021
Ways To Reach Goal
Moderate
Asked in companies
A virus travels on a positive number line with a range from 0 to ‘R’ in which it can travel only in the left or right direction. You are given a string ‘PATH’ representing the sequence of moves a virus can move. Your task is to find the number of distinct subsequences of those moves that lead from a given point ‘X’ to point ‘Y’ on the number line. If a virus is present at position ‘P’, then moving in the ‘l’ direction will take it to the ‘P’ - 1 position, whereas moving in the ‘r’ direction will take it to the ‘P’ + 1 position.
Note:
Subsequences are created by deleting 0 or more characters from a sequence without changing the order.
Example:
Let ‘PATH’ be: "rrr"
Let ‘X’ = 1, ‘Y’ = 2, and ‘R’ = 10
Paths are ["r", "r", "r"]. As we have to choose distinct subsequences, so the result is 1.
Input Format :
The first line of input contains an integer ‘T’, the number of test cases.
The first line of each test case contains a string ‘PATH’, representing the sequence of moves.
The second of each test case contains three space-separated integers ‘X’, ‘Y’, and ‘R’, representing the start position, end position, and the range of number line.
Output Format :
For each test case, print a single integer representing the number of distinct subsequences modulo (10^9 + 7).
Print output of each test case in a separate line.
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 <= |PATH| <= 10^3
0 <= X, Y < R <= 2500
'PATH' contains only two characters 'r' and 'l'.
Time Limit: 1 sec
Approaches
The basic idea is to check whether it is possible to reach from position ‘X’ to ‘Y’ using all possible subsequences of the moves. We also use a set to count only the distinct subsequences.
Here is the algorithm :
- Create a set (say, ‘S’) that will store the subsequences of the string.
- Call the HELPER function to calculate the count.
- Return the value returned by the HELPER function.
HELPER(PATH, X, Y, R, IDX, S, TEMP) (where ‘PATH’, ‘X’, ‘Y’, AND ‘R’ are given variables, ‘IDX’ is the current index of string, ‘S’ the set, ‘TEMP’ is the current subsequence.)
- Base case
- Check if ‘IDX’ is equal to the length of ‘PATH’.
- Check if the current subsequence is valid or not using the CHECK function and not present in the set.
- Insert the current subsequence in the set ‘S’.
- Return 1
- Else, return 0.
- Check if the current subsequence is valid or not using the CHECK function and not present in the set.
- Check if ‘IDX’ is equal to the length of ‘PATH’.
- Create the subsequence recursively by including and excluding the current character.
- Add the result of both ways.
CHECK(TEMP, X, Y, R) (where ‘TEMP’ is the string to be checked, ‘X’, ‘Y’, and ‘R’ are given variables.)
- Run a loop from 0 to the size of ‘TEMP’ (say, iterator ‘i’)
- Check if the current character of ‘TEMP’ is ‘L’
- Decrement ‘X’ by 1.
- Else, increment ‘X’ by 1.
- Check if ‘X’ lies in range.
- Check if the current character of ‘TEMP’ is ‘L’
- Return whether ‘X’ is equal to ‘Y’ or not.
The basic idea is to use memoization to reduce the recursive calls. We have two options while creating a subsequence, i.e., to pick a current character or ignore it. The duplicates arise because while considering a subsequence, we ignore a character and then pick that same character in the next move. We create a ‘DP’ array to avoid this.
We define ‘DP[IDX][X][FLAG] that represents the count of unique subsequences of ‘PATH[IDX]’ that starts from position ‘X’, and ‘FLAG’ represents the previous direction we moved.
We can have four different choices for ‘FLAG’:
- We took ‘R’ direction.
- We took ‘L’ direction.
- We took both of them.
- We took none of them.
Here is the algorithm :
- Create an array (say, ‘DP’) to do the memoization and initialize with -1.
- Call the HELPER function two times.
- When the first direction taken is ‘L’
- When the first direction taken is ‘R’.
- Add both the values to the result (say, ‘RES’).
- Check if ‘X’ is equal to ‘Y’
- Increment ‘RES’ by 1.
- Finally, return ‘RES’.
HELPER(PATH, IDX, FLAG, X, Y, R) (where ‘PATH’, ‘X’, ‘Y’, and ‘R’ are given variables, ‘IDX’ is the current index of string, ‘FLAG’ represents the previous direction taken).
- Base case
- Check if ‘X’ lies in range.
- Check if ‘IDX’ is smaller than the length of ‘PATH’.
- Case 1: when ‘L’ is chosen.
- Call recursive function two times to add the value when the next direction can be ‘L’ or ‘R’.
- Case 2: when ‘R’ is chosen.
- Call recursive function two times to add the value when the next direction can be ‘L’ or ‘R’.
- Case 3: when both are not chosen.
- Store the value of the result in ‘DP’ to memoize.
- Finally, return result.
Similar problems