Given a number line from 0 to n and a string denoting a sequence of moves, determine the number of subsequences of those moves that lead from a given point x to end at another point y.
Moves will be given as a sequence of 'l' and 'r' instructions:
'l' → Left movement (j → j - 1) 'r' → Right movement (j → j + 1)
Example Input:
Number line: 0 to 6 Moves sequence: "rrlrlr" Start position: x = 1 End position: y = 4
Output:
3 (There are 3 subsequences that reach from 1 to 4)
Notes: 0 and n are the lower and upper limits of number line, you cannot exceed those. The answer should be returned modulo (10⁹ + 7).
Can anyone help with this.
well brute is easy but cant think of optimal solution.
Where does this question come from, I want to know.
How large is $$$n$$$? There is obviously $$$O(n^3)$$$ DP, but I doubt n is only 1e3.
we can dfs and find the ans and use a visited (index , pos , hash) for distinct values ?