# Count Unique Subsequences to Destination?

Computer Science Asked by HCSF on July 25, 2020

I am looking at this post:

Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n.

In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string, s, of movement instruction consisting of the letters l and r, where l is an instruction to move one step left and r is an instruction to move one step right. Jamie followed the instructions in s one by one and in order. For example if s=‘rrlr’, she performs the following sequence of moves:
one step right ->one step right ->one step left -> one step right. Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. Recall that a subsequence of a string is obtained by deleting zero or more characters from string.

It has four parameters

• A String , s giving a sequence of moves using the characters l( i.e. move left one unit ) and r (i.e. move right one unit)
• An integer n, denoting the length of the number line.
• An integer x, denoting Jamie’s starting point on the number line
• An integer y , denoting Jamie’s ending point on the number line.

The function must return an integer denoting the total number of distinct subsequence of strings that will lead Jamie from point x to point y as this value can be quite large.

Sample Input
rrlrlr

6

1

2

output = 7

Let’s add few more constraints to simply the questions:

• 1 <= length of s <= 10^3
• 0 <= x, y < n <= 2500

I wonder what the runtime is for the proposed solution there:

int distinctSequences (int n, int a, int b, const std::string& actions) {
auto res{0};

if (a > 0) {
}

if (a < n) {
}

for (auto c: actions) {

if (c == 'r') {
for (auto [pos, count]: readyForR) {
auto pp1{pos+1};

if (pp1 == b) res += count;
}

} else {
for (auto [pos, count]: readyForL) {
auto pm1{pos-1};

if (pm1 == b) res += count;
}

}
}

return res;
}


What’s its runtime complexity?

## Related Questions

### How to generate graphs with a Hamiltonian path?

3  Asked on February 21, 2021 by always-newbie

### Wifi throughput calculation

1  Asked on February 20, 2021 by copsa

### Searching for points near given point in a multidimensional space

1  Asked on February 20, 2021 by saku

### Group adjacent sections to create groups with biggest value, value is changing in groups

1  Asked on February 20, 2021 by rossko_dca

### Thirty-one game. Prediction of the winner

1  Asked on February 17, 2021 by donvitomarco

### Explanation of conventional solutions to the Firing Squad Synchronization problem

0  Asked on February 16, 2021 by von-spotz

### If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare?

1  Asked on February 13, 2021 by aviv-barel

### How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

5  Asked on February 10, 2021 by gizmo

### Complexity of a cutting operation on a list of binary trees

0  Asked on February 10, 2021 by arthur-b

### speed of preorder traversal

1  Asked on February 8, 2021 by keith-paton

### Mergesort and some claims on comparison

1  Asked on February 7, 2021 by user3661613

### Proving the language of non-primes is in NP

1  Asked on February 6, 2021 by builderthebob00

### Does writing more data to disk consume more energy than writing less?

0  Asked on February 5, 2021 by pookie

### In Strassen’s algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

1  Asked on February 4, 2021 by retsek680

### How to find the language of a CFG from Production rules

1  Asked on February 3, 2021 by stark2022

### Machine Learning algorithm for predicting a user’s rating on an item?

0  Asked on February 1, 2021 by david-grnberger

### Finding the Hamiltonian cycle that uses the least amount of straight lines

0  Asked on January 30, 2021 by tzlil

### Can I have 2 free adjacent nodes in the fit algorithm for data management

0  Asked on January 29, 2021 by angelic-demonic

### Longest path on a full tree

1  Asked on January 27, 2021 by bm1125