FastPrepDistinct Moves
Problems/Distinct Moves

Distinct Moves

Meesho logoMeesho● HardOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

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

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 position j - 1, and an instruction 'r' moves to position j + 1.
  • You must stay on the number line: a subsequence counts only if every position you visit, from x to y, is between 0 and n.

Complete the function distinctMoves in the editor with the following parameters:

  • 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

The function returns an int: the number of distinct subsequences modulo 109 + 7.

Function

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

Examples

Example 1

s = "rrlrlr"n = 6x = 1y = 2return = 7
Example 1 illustration

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| ≤ 103
  • s contains only the characters 'l' and 'r'.
  • 0 ≤ x, y < n ≤ 2500

More Meesho interview questions

  • Efficient DeploymentsOA · Seen Jun 2026

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
See Meesho hiring insights
Saved
class Solution {
    public int distinctMoves(String s, int n, int x, int y) {
      // write your code here
    }

}
Checking account…