Problem

Distinct Number Line Moves

MicrosoftFULLTIMEOA
See Microsoft hiring insights

You are given a number line with positions labeled from 0 to n, a string s of move instructions, and two positions x and y.

A move instruction 'l' moves one step left, and 'r' moves one step right. You may choose any subsequence of s, preserving order, and execute that subsequence starting from position x. The position must always remain between 0 and n.

Two subsequences are considered the same if their resulting move strings are identical, even if they came from different indices of s.

Return the number of distinct subsequence move strings that take you from x to y, modulo 1_000_000_007.

Examples
01 · Example 1
s = "rrlrlr"
n = 6
x = 1
y = 2
return = 7
Constraints
  • 1 <= s.length <= 10^5
  • 0 <= x, y, n <= 2500
  • s contains only 'l' and 'r'.
More Microsoft 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
sign in to submit