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.

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.

Examples

Example 1

1
2
3
4

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

1
2

Input: s = "10"
Output: "10"

Constraints

  • 1 <= s.length <= 50
  • s[i] is either '0' or '1'.
  • s is a special binary string.

Solution

Method 1 - Recursive Divide and Conquer

Intuition: To get the lexicographically largest string, we need to place larger special substrings before smaller ones. A special binary string can be decomposed into consecutive special substrings, and we can recursively optimize each part.

Approach:

  1. Find all consecutive special substrings at the current level
  2. For each special substring of the form “1…0”, recursively optimize its inner part
  3. Sort all special substrings in descending order to get lexicographically largest arrangement
  4. Concatenate the sorted substrings

Key insight: Every special binary string either:

  • Is “10” (base case)
  • Can be split into consecutive special substrings that can be rearranged

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string makeLargestSpecial(string s) {
    if (s.length() <= 2) return s;
    
    vector<string> substrings;
    int count = 0, start = 0;
    
    for (int i = 0; i < s.length(); i++) {
        count += (s[i] == '1') ? 1 : -1;
        if (count == 0) {
            // Found a complete special substring from start to i
            string inner = s.substr(start + 1, i - start - 1);
            substrings.push_back("1" + makeLargestSpecial(inner) + "0");
            start = i + 1;
        }
    }
    
    // Sort in descending order for lexicographically largest result
    sort(substrings.begin(), substrings.end(), greater<string>());
    
    string result = "";
    for (const string& sub : substrings) {
        result += sub;
    }
    return result;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import (
    "sort"
    "strings"
)

func makeLargestSpecial(s string) string {
    if len(s) <= 2 {
        return s
    }
    
    var substrings []string
    count := 0
    start := 0
    
    for i := 0; i < len(s); i++ {
        if s[i] == '1' {
            count++
        } else {
            count--
        }
        if count == 0 {
            inner := s[start+1 : i]
            substrings = append(substrings, "1"+makeLargestSpecial(inner)+"0")
            start = i + 1
        }
    }
    
    sort.Slice(substrings, func(i, j int) bool {
        return substrings[i] > substrings[j]
    })
    
    return strings.Join(substrings, "")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import java.util.*;

class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() <= 2) return s;
        
        List<String> substrings = new ArrayList<>();
        int count = 0, start = 0;
        
        for (int i = 0; i < s.length(); i++) {
            count += (s.charAt(i) == '1') ? 1 : -1;
            if (count == 0) {
                String inner = s.substring(start + 1, i);
                substrings.add("1" + makeLargestSpecial(inner) + "0");
                start = i + 1;
            }
        }
        
        Collections.sort(substrings, Collections.reverseOrder());
        
        StringBuilder result = new StringBuilder();
        for (String sub : substrings) {
            result.append(sub);
        }
        return result.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun makeLargestSpecial(s: String): String {
        if (s.length <= 2) return s
        
        val substrings = mutableListOf<String>()
        var count = 0
        var start = 0
        
        for (i in s.indices) {
            count += if (s[i] == '1') 1 else -1
            if (count == 0) {
                val inner = s.substring(start + 1, i)
                substrings.add("1" + makeLargestSpecial(inner) + "0")
                start = i + 1
            }
        }
        
        substrings.sortDescending()
        
        return substrings.joinToString("")
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def makeLargestSpecial(s: str) -> str:
    if len(s) <= 2:
        return s
    
    substrings = []
    count = 0
    start = 0
    
    for i, char in enumerate(s):
        count += 1 if char == '1' else -1
        if count == 0:
            inner = s[start + 1:i]
            substrings.append("1" + makeLargestSpecial(inner) + "0")
            start = i + 1
    
    # Sort in descending order for lexicographically largest result
    substrings.sort(reverse=True)
    
    return ''.join(substrings)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

pub fn make_largest_special(s: String) -> String {
    if s.len() <= 2 {
        return s;
    }
    
    let mut substrings = Vec::new();
    let mut count = 0;
    let mut start = 0;
    let chars: Vec<char> = s.chars().collect();
    
    for i in 0..chars.len() {
        count += if chars[i] == '1' { 1 } else { -1 };
        if count == 0 {
            let inner: String = chars[start + 1..i].iter().collect();
            let sub = format!("1{}0", make_largest_special(inner));
            substrings.push(sub);
            start = i + 1;
        }
    }
    
    substrings.sort_by(|a, b| b.cmp(a)); // Sort in descending order
    
    substrings.join("")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

function makeLargestSpecial(s: string): string {
    if (s.length <= 2) return s;
    
    const substrings: string[] = [];
    let count = 0;
    let start = 0;
    
    for (let i = 0; i < s.length; i++) {
        count += s[i] === '1' ? 1 : -1;
        if (count === 0) {
            const inner = s.substring(start + 1, i);
            substrings.push("1" + makeLargestSpecial(inner) + "0");
            start = i + 1;
        }
    }
    
    // Sort in descending order for lexicographically largest result
    substrings.sort((a, b) => b.localeCompare(a));
    
    return substrings.join("");
}

Complexity

  • ⏰ Time complexity: O(n² log n) where n is the length of the string (recursive calls + sorting)
  • 🧺 Space complexity: O(n²) for recursion stack and substring storage