Count Distinct Subsequences to Reach Target Position

Revision en1, by shawsk, 2025-03-01 10:56:39

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shawsk 2025-03-01 10:56:39 756 Initial revision (published)