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) {
std::unordered_map<int, int> readyForR, readyForL;
auto res{0};
if (a > 0) {
readyForL.emplace(a, 1);
}
if (a < n) {
readyForR.emplace(a, 1);
}
std::unordered_map<int, int> nextReadyForR, nextReadyForL;
for (auto c: actions) {
nextReadyForR.clear();
nextReadyForL.clear();
if (c == 'r') {
for (auto [pos, count]: readyForR) {
auto pp1{pos+1};
nextReadyForR.emplace(pp1, count);
readyForL[pp1] += count;
if (pp1 == b) res += count;
}
nextReadyForR.erase(n);
std::swap(readyForR, nextReadyForR);
} else {
for (auto [pos, count]: readyForL) {
auto pm1{pos-1};
nextReadyForL.emplace(pm1, count);
readyForR[pm1] += count;
if (pm1 == b) res += count;
}
nextReadyForL.erase(0);
std::swap(readyForL, nextReadyForL);
}
}
return res;
}
```

What’s its runtime complexity?

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP