Special Binary String


  • 0

    Click here to see the full article post


  • 0
    L

    @awice, Thanks for adding intuition part, that really helps.


  • 0
    C

    The current solution is missing the recursive call. mountains.append("1{}0".format(S[anchor + 1: i])) should be mountains.append("1{}0".format(self.makeLargestSpecial(S[anchor + 1: i])))

    Having said that, wouldn't the time complexity be O(n^2) for a uniformly increasing -> decreasing mountain? You'd be making n/2 calls iterating across n, n-2, n-4... elements.


  • 0

    @cyap Thanks for the correction, fixed.


  • 0
    L

    @cyap, the recursive call is already made when processing those mountains.


  • 0
    C

    @LeonCheng It wasn't. You can test it yourself: use both lines of code in my first post with default test case, and you'll see that the first returns an incorrect solution, while the second one returns the correct one.

    Explanation: While iterating across the binary string, you add 1 to your balance for every '1' and subtract 1 for every '0'. The default test case is '11011000'. You can see that you on your first iteration, you will never hit a balance of 0 until the very end because all the 1s are front-loaded. Thus, without a recursive call, you will therefore end up with a single mountain: the entire binary string, and the answer will be the input string.

    When you add the recursive call, you take away the leading 1 and trailing 0, and upon iterating on the ensuing substring, immediately hit a balance of 0 from the first mountain (and eventually the second mountain).


  • 0
    I

    @awice how can I analyze time complexity of this problem to get to O(n^2)?


  • 0

    @invalid Worst case, we will touch n-2 elements in each level of recursion, so the total amount of work would be:

    n + (n-2) + (n-4) + ... 4 + 2 = sum of even numbers through n ~= O(n^2)


Log in to reply
 

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