0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Welcome to CS@SE. You have found tag runtime-analysis: what has been your exposure to the formalisms? What is your current assessment of the solution you present? $\endgroup$ – greybeard Jul 25 '20 at 2:58
  • $\begingroup$ @greybeard more than a decade ago, I needed to do formal proofs for runtime at school as an undergrad. getting rusty after a decade, so like to see some formal analysis. It looks like O(n^2) to me. But not 100% sure. Hence, looking for some formal analysis here. $\endgroup$ – HCSF Jul 25 '20 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.