Distinct Moves
Updated
Problem statement
You are given a number line with positions labeled from 0 to n, and a sequence of moves s made of the instructions 'l' (move left by 1) and 'r' (move right by 1). Count how many distinct subsequences of these moves take you from the starting position x to the ending position y. Return the result modulo 109 + 7.
Notes:
- A subsequence is formed by deleting zero or more elements from the original sequence without changing the order of the remaining elements. Deleting every element gives the empty subsequence, which makes no moves, so it counts when
x = y. - 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
'rl'in'rrl'is counted only once. - Starting at position
j, an instruction'l'moves to positionj - 1, and an instruction'r'moves to positionj + 1. - You must stay on the number line: a subsequence counts only if every position you visit, from
xtoy, is between0andn.
Complete the function distinctMoves in the editor with the following parameters:
string s: the sequence of movesint n: the upper bound of the number lineint x: the starting pointint y: the ending point
The function returns an int: the number of distinct subsequences modulo 109 + 7.
Function
distinctMoves(s: String, n: int, x: int, y: int) → intExamples
Example 1
s = "rrlrlr"n = 6x = 1y = 2return = 7
Start at 1 and end at 2, so a subsequence must have exactly one more 'r' than 'l'. The distinct ones that stay between 0 and 6 are: "r", "rrl", "rlr", "lrr", "rrllr", "rrlrl" and "rlrlr". That is 7.
Constraints
1 ≤ |s| ≤ 103scontains only the characters'l'and'r'.0 ≤ x, y < n ≤ 2500
More Meesho interview questions
Similar questions at other companies
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
- Minimum Merge ConflictsAmazon · OA
- String Formation (Also for AI/ML Software Engineer Intern :)Snowflake · OASnowflake interview questions
- Longest Subsequence which is a SubstringSalesforce · OASalesforce interview questions
- Compressed Representation SizeMicrosoft · OAMicrosoft interview questions
- Find Minimum OperationsIBM · OAIBM interview questions
- String Challenge (Generic)TikTok · OATikTok interview questions
- Maximize the Lottery IDCitadel · OACitadel interview questions
- Sum of All ValuesFlexport · OAFlexport interview questions
- Maximum Crayon Removal ScoreWells Fargo · OAWells Fargo interview questions