Special Binary String - Leetcode Solution

Problem Statement: A string is called special if all its sub sequences are non-empty and distinct. A string can be generated using the following rules:

1. The string is 1 if the input is empty
2. The string is formed by adding two special strings together
3. The string is formed by enclosing a special string within parentheses

A binary string is a string of 0's and 1's. Given a binary string s, return any special binary string of s.

Example: Input: s = "11011000" Output: "11100100" Explanation: The input string can be represented as follows: "11011000" = "1" + "10" + "(1100)" + "00" "11100100" = "1" + "11" + "(10)" + "01" + "00" Both strings are special as all their sub sequences are non-empty and distinct.

Solution:

To solve this problem, we can use a recursive approach. We can divide the binary string s into its special binary sub-strings recursively.

The main concept here is that we have to build a special binary string. To do that, we will start by sorting all of the substrings of s in decreasing order based on their length. This will give us two special sub-strings that we can work with- the first and the last substrings in the sorted list.

We will consider these two substrings in isolation and form the final string by combining them. There are two cases to consider:

1. If the first substring starts with a 1 and ends with a 0, then we can keep it as it is.
2. If the first substring starts with a 0 and ends with a 1, then we need to reverse it, change all the 0's to 1's and all the 1's to 0's, and then enclose this new substring in parentheses.

After processing the first substring, we can then recursively call the function on the rest of the string, which would be between the processed first substring and the unprocessed last substring.

Lastly, we can return the final special binary string by combining the processed first substring, the middle recursive calls, and the processed last substring.

Code:

def makeLargestSpecial(s: str) -> str: def dfs(s): if s == '': return '' res, stk = [], [] for i, ch in enumerate(s): stk.append(ch) if stk.count('1') == stk.count('0'): res.append('1' + dfs(s[i+1:]) + '0') stk, res = [], sorted(res, reverse=True) return ''.join(res) return dfs(s)

Time Complexity: O(nlogn) Space Complexity: O(n)

The time complexity of this solution is O(nlogn), where n is the length of the binary string s. Firstly, we sort all the sub-strings in decreasing order, which takes O(nlogn) time. Then, we apply the dfs function recursively to build the final string, which takes O(n) time. Hence, the overall time complexity is O(nlogn).

The space complexity of this solution is also O(n), as we are using a stack and a list to store intermediate results.

1