FastPrepFastPrep
Problem Brief

Distinct Moves

FULLTIMEOA

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. An instruction l = left movement, so from position j the new position is j - 1, an instruction r = right movement, so from position j the new position would be j + 1.

For example, given a number line from 0 to 6, and a sequence of moves rrlrr, the number of subsequences that lead from 1 to 4 on the number line is 3.

Function Description

Complete the function distinctMoves in the editor.

distinctMoves has the following parameter(s):

  1. s: a string that represents a sequence of moves
  2. n: an integer that represents the upper bound of the number line
  3. x: an integer that represents the starting point
  4. y: an integer that represents the ending point

Returns

int: the number of distinct subsequences modulo 10^9 + 7

1Example 1

Input
s = "rrlrlr", n = 6, x = 1, y = 2
Output
7
Explanation
N/A

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= |s| <= 10^3
  • 0 <= x, y, n <= 2500
public int distinctMoves(String s, int n, int x, int y) {
  // write your code here
}
Input

s

"rrlrlr"

n

6

x

1

y

2

Output

7

Sign in to submit your solution.