Special binary strings are binary strings with the following two properties:
0's is equal to the number of 1's.1's as 0's.You are given a special binary string s.
A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.
Return the lexicographically largest resulting string possible after applying the mentioned operations on the string.
Example 1:
Input: s = "11011000" Output: "11100100" Explanation: The strings "10" [occuring at s[1]] and "1100" [at s[3]] are swapped. This is the lexicographically largest string possible after some number of swaps.
Example 2:
Input: s = "10" Output: "10"
Constraints:
1 <= s.length <= 50s[i] is either '0' or '1'.s is a special binary string.This approach leverages recursion to decompose the special binary string into smaller special substrings, sort these components, and then rebuild the string to achieve the lexicographically largest string. This works because by sorting the special substrings in descending order, larger lexicographical strings are formed.
The function recursively decomposes the string whenever a balance point is reached, i.e., when the count of '1's and '0's becomes zero. Once parts are decomposed, they are sorted in reverse (descending) order to achieve the lexicographically largest string.
Java
C++
C
C#
JavaScript
Time Complexity: O(n^2), where n is the length of the string, due to recursive decomposition and sorting.
Space Complexity: O(n), for storing the results and recursion stack.
Add Binary - Leetcode 67 - Python • NeetCode • 73,772 views views
Watch 9 more video solutions →Practice Special Binary String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor