Student Attendance Record II


  • 0

    Click here to see the full article post


  • 0

    Approach 5 has a typo. i should range from 0 to n. Not to n-1.


  • 0

    I have corrected it. Thanks


  • 0
    E

    Hi. You insert a P before the ---LLL in order to make the f[n-3] string rewardable. I don't understand this. If the f[n-3] string "bleeding" into the L or LL of the ---LLL makes the f[n-3] string unrewardable, then why doesn't the first of the four cases (---LPL) have the same issue, where an f[n-5] string ending in LL would also "bleed" into the last characters, creating ---LLLPL?


  • 0

    @elle First Fix 'P' at last position (----P), this will result f[n-1]. Now fix 'L' at the last position, out of all valid f[n-1] strings, only strings ending with PLL should not be considered as it will lead to --PLLL strings which is not valid. Thus it results in f[n-1]-f[n-4] and total of 2f[n-1]-f[n-4]. Please let me know if you still have some question?


  • 0
    E

    Thanks for your reply. Why fix an additional P to make ---PLLL? Isn't ---LLLL also invalid? The final recurrence relation is absolutely correct, but I'm not sure this is the correct explanation. I can explain a simpler way to get to 2f[n-1]-f[n-4] but first I would like to understand yours. By the way, that's a typo in the graphic, writing "N" for the right branch instead of "P", right?


  • 0

    @elle This is because, we need to consider only those strings which are rewardable at the length (n-3) but become unrewardable at a length(n-1)(for left branch ). Only the strings ending with a P at length (n-3) and ending with PLL of the left branch at length (n-1) follow this criteria. Could you please share your simpler explanation?


  • 0
    E

    Right. So consider the 1st of the 4 branches: [n-3]LPL. A string like PPPPPPPPPPPPPPPLLLPL would be rewardable at [n-3] but fail at [n-1], would it not? That was my original question: Under your approach, why doesn't the 1st branch get considered as a "rewardable at [n-3] but unrewardable at [n-1]" case? Maybe your criterion is more specific but not fully stated; I would like to understand that part.


  • 0
    E

    The simpler way, IMHO, and compliments to N. Shade at math.stackexchange.com, is to consider the cases (a) ------P, (b) ------PL, and (c) ------PLL. A minute of thought will reveal that these are mutually exclusive. It's also realized that going further, e.g. (d) ------PLLL, becomes useless because the string will always be unrewardable. So the whole of f[n] may be summarized by (a) + (b) + (c), in other words, f[n] = f[n-1] + f[n-2] + f[n-3]. This means also that f[n-1] = f[n-2] + f[n-3] + f[n-4]. If you subtract the latter from the former to cancel out the f[n-2] and f[n-3] cases, then you are left with f[n] = 2 f[n-1] - f[n-4].


  • 0
    N

    Space complexity of brute force approach is wrong it cannot be O(n^n) unless you store all the entries, which you are not doing.
    Space complexity will remain O(n) which is equal to depth of the tree.


  • 0
    W

    Can anyone prove the mod operation in detail? (f[i] = ((2 * f[i - 1]) % M + (M - f[i - 4])) % M;)
    why is the result still right after we did three mod operations each time ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.