Special Binary String



The current solution is missing the recursive call.
mountains.append("1{}0".format(S[anchor + 1: i]))
should bemountains.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, n2, n4... elements.



@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 frontloaded. 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).


@invalid Worst case, we will touch n2 elements in each level of recursion, so the total amount of work would be:
n + (n2) + (n4) + ... 4 + 2 = sum of even numbers through n ~= O(n^2)