shawsk's blog

Count Distinct Subsequences to Reach Target Position
By shawsk, history, 14 months ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

well brute is easy but cant think of optimal solution.

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Where does this question come from, I want to know.

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How large is $$$n$$$? There is obviously $$$O(n^3)$$$ DP, but I doubt n is only 1e3.

→ Reply
»
6 months ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

we can dfs and find the ans and use a visited (index , pos , hash) for distinct values ?

→ Reply