Ways To Reach Goal

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
5 upvotes
Asked in companies
ShareChatCultfit

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
rrlrlr
1 2 10
rrr
1 2 10
Sample Output 1 :
7
1
Explanation For Sample Input 1 :
For test case 1: 
Paths are: ["r", "rlr", "lrr", "rrl", "rlrlr", "rrllr", "rrlrl"]

For test case 2: 
Paths are ["r", "r", "r"]. As we have to choose distinct subsequences, so the result is 1.
Sample Input 2 :
2
rrlr
1 2 15
rrrlrr 
0 0 7
Sample Output 2 :
3
2
Hint

Try to check for all the subsequences.

Approaches (2)
Recursion

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 :
 

  1. Create a set (say, ‘S’) that will store the subsequences of the string.
  2. Call the HELPER function to calculate the count.
  3. 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.)

 

  1. 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.
  2. Create the subsequence recursively by including and excluding the current character.
  3. 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.)
 

  1. 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.
  2. Return whether ‘X’ is equal to ‘Y’ or not.
Time Complexity

O((2^N)*N), where ‘N’ is the length of the string.
 

For each subsequence, we have two options to include the current character or not, which can take 2^N time, and for each subsequence, we check whether using moves of that subsequence we reach ‘Y’, which takes ‘N’ time. Therefore, the overall time complexity will be O((2^N)*N).

Space Complexity

O(N), where ‘N’ is the length of the string.

 

The recursion stack can contain the size of the string ‘PATH’, which is ‘N’. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Ways To Reach Goal
Full screen
Console