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?