FastPrep
Problem · Dynamic Programming

Distinct Moves

Learn this problem
● HardMeeshoOA

Problem statement

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

    distinctMoves(s: String, n: int, x: int, y: int) → int

    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! 🙏

    Examples

    Example 1

    s = "rrlrlr"n = 6x = 1y = 2return = 7
    Example 1 illustration
    Part of the image explanation:

    Constraints

    • 1 ≤ |s| ≤ 10^3
    • 0 ≤ x,y,n ≤ 2500

    More Meesho problems

    drafts saved locally
    public int distinctMoves(String s, int n, int x, int y) {
  // write your code here
}
    s"rrlrlr"
    n6
    x1
    y2
    expected7
    checking account