FastPrepFastPrep
Problem Brief

Distinct Moves

OA

Given a number line with positions labeled from 0 to n, and a sequence of movements consisting of instructions 'l' (move left by 1) and 'r' (move right by 1), determine how many distinct subsequences of these moves will take you from a starting position x to an ending position y. Return the result modulo (10^9 + 7).

Notes:

  • A subsequence is formed by deleting zero or more elements from the original sequence without changing the order of the remaining elements.
  • A subsequence is distinct if its sequence of characters differs from another subsequence. Subsequences with identical characters from different indices are considered the same and counted only once, e.g., the subsequence containing 'l' in 'rlr' is only counted once.
  • Starting at position j, an instruction 'l' moves to position j - 1, and an instruction 'r' moves to position j + 1.

    • Function Description

    Complete the function distinctMoves in the editor with the following parameter(s):

    • string s: the sequence of moves
    • int n: the upper bound of the number line
    • int x: the starting point
    • int y: the ending point

    Returns

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

    A huge thanks to the friend who shared the source! 🙏

    1Example 1

    Input
    s = "rrlrlr", n = 6, x = 1, y = 2
    Output
    7
    Explanation
    Example 1 illustration
    Part of the image explanation:

    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.