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^50 <= x, y, n <= 2500scontains only'l'and'r'.
More Microsoft problems
- Rank Open BusinessesPHONE SCREEN · Seen May 2026
- Retain Top K ValuesPHONE SCREEN · Seen May 2026
- In-Memory SQL with CSV InitializationONSITE INTERVIEW · Seen May 2026
- Order Records by Matching Start and EndONSITE INTERVIEW · Seen May 2026
- Recover Corrupted Master PageONSITE INTERVIEW · Seen Feb 2026
- Get Minimum TimeSeen Jun 2025
- Count Subarrays with Bitwise OR PresentSeen Jun 2025
- Get Max Or SumSeen Jun 2025
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