Special Binary String — LeetCode 761 Python Solution

The problem

Special binary strings are binary strings with the following two properties: The number of 0's is equal to the number of 1's. Every prefix of the binary string has at least as many 1's as 0's.

Example

Input

s = "11011000"

Output

"11100100"

Explanation

The strings "10" [occuring at s[1]] and "1100" [at s[3]] are swapped.

Python solution

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        if s == '':
            return ''
        ans = []
        cnt = 0
        i = j = 0
        while i < len(s):
            cnt += 1 if s[i] == '1' else -1
            if cnt == 0:
                ans.append('1' + self.makeLargestSpecial(s[j + 1 : i]) + '0')
                j = i + 1
            i += 1
        ans.sort(reverse=True)
        return ''.join(ans)

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 761. Special Binary String is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems