# Special Binary String
**Difficulty:** HARD
[External](https://leetcode.com/problems/special-binary-string)
Canonical: https://scaleengineer.com/dsa/problems/special-binary-string
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** String
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [UKG](https://scaleengineer.com/companies/ukg), [Grammarly](https://scaleengineer.com/companies/grammarly), [Coursera](https://scaleengineer.com/companies/coursera)
---
## 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_.

**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 <= 50`
* `s[i]` is either `'0'` or `'1'`.
* `s` is a special binary string.

# Approaches
## Brute-Force State Space Search
This approach treats the problem as a state space search on a graph. Each unique special binary string that can be formed is a node, and a 'move' (swapping two consecutive special substrings) is an edge. Starting from the input string `s`, we can explore all reachable strings using a traversal algorithm like Breadth-First Search (BFS). We maintain a set of visited strings to avoid redundant computations and cycles. The lexicographically largest string encountered during this exploration is the result.
**Time:** O(C(N) * N^4), where C(N) is the number of states. Generating neighbors for one string takes O(N^4) and there are C(N) states. This is computationally infeasible. · **Space:** O(C(N) * N), where C(N) is the number of reachable special binary strings of length N. This is prohibitively large.
**Pros:** Conceptually simple and directly follows the problem statement.; Guaranteed to find the correct answer if given enough time and memory.
**Cons:** Extremely inefficient due to the massive number of possible strings (states).; The complexity of generating all possible moves from a single string is high.; Infeasible for the given constraints (`N` up to 50).
### Explanation
The core of this method is to systematically generate every possible string that can be reached from the initial string `s` through a series of swaps. We can use a queue to manage the strings to visit. For each string we process, we scan it to find all possible valid moves. A move is defined by finding a substring that is itself a concatenation of two smaller, consecutive special strings, say `S1` and `S2`. We then swap them to form `S2S1`, creating a new string. This new string is a neighbor in our state graph. If we haven't seen this new string before, we add it to our queue to be processed later. Throughout this process, we keep track of the lexicographically greatest string seen. While correct in theory, the number of special binary strings of length `N` is related to the Catalan numbers, which grow exponentially, making the state space far too large to explore for `N=50`.

```java
// This is a conceptual illustration. A full implementation would be too slow to pass.
public String makeLargestSpecial(String s) {
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.add(s);
    visited.add(s);
    String maxS = s;

    while (!queue.isEmpty()) {
        String current = queue.poll();
        // Generate all possible next strings from 'current'
        List<String> neighbors = generateNeighbors(current);
        for (String nextS : neighbors) {
            if (!visited.contains(nextS)) {
                visited.add(nextS);
                queue.add(nextS);
                if (nextS.compareTo(maxS) > 0) {
                    maxS = nextS;
                }
            }
        }
    }
    return maxS;
}

private List<String> generateNeighbors(String s) {
    List<String> neighbors = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j <= s.length(); j++) {
            String sub = s.substring(i, j);
            // Try all splits of 'sub' into S1 and S2
            for (int k = 1; k < sub.length(); k++) {
                String s1 = sub.substring(0, k);
                String s2 = sub.substring(k);
                if (isSpecial(s1) && isSpecial(s2)) {
                    String neighbor = s.substring(0, i) + s2 + s1 + s.substring(j);
                    neighbors.add(neighbor);
                }
            }
        }
    }
    return neighbors;
}

private boolean isSpecial(String str) {
    if (str.length() % 2 != 0) return false;
    int balance = 0;
    for (char c : str.toCharArray()) {
        if (c == '1') {
            balance++;
        } else {
            balance--;
        }
        if (balance < 0) return false; // Prefix has more 0s
    }
    return balance == 0; // Equal number of 1s and 0s
}
```
### Algorithm
1.  Model the problem as a graph where nodes are unique special binary strings and edges represent a valid 'move'.
2.  Initialize a queue for Breadth-First Search (BFS) and a `visited` set. Add the initial string `s` to both.
3.  Keep track of the lexicographically largest string found so far, initialized to `s`.
4.  While the queue is not empty:
    a. Dequeue a string `current`.
    b. Generate all possible next strings by finding all pairs of consecutive special substrings `S1` and `S2` within `current` and swapping them.
    c. To do this, iterate through all substrings of `current`, and for each substring, check if it can be split into two special substrings.
    d. A helper function `isSpecial(str)` is required to verify if a string is special.
5.  For each new valid string `next` generated:
    a. If `next` has not been visited, add it to the queue and `visited` set.
    b. Update the overall maximum string if `next` is lexicographically larger.
6.  The largest string found after the traversal is the answer.

## Recursive Divide and Conquer
A much more efficient approach is to use recursion based on the definition of special binary strings. Any special string `S` can be seen as a concatenation of primitive special strings, `S = P1P2...Pk`. A key insight is that the 'move' operation allows us to reorder these primitive components `P1, ..., Pk` arbitrarily. To achieve the lexicographically largest string, we should arrange these components in descending lexicographical order.

Furthermore, each primitive component `Pi` has the structure `1M0`, where `M` is itself a concatenation of special strings. To make `Pi` as large as possible, we need to make `M` as large as possible. This suggests a recursive strategy: to solve for `S`, we first find its primitive components, recursively find the largest form of each component's inner part, and then sort these maximized components.
**Time:** O(N^2). The string is scanned at each level of recursion. String slicing and sorting contribute to the complexity. A loose upper bound is O(N^2), which is sufficient for N=50. · **Space:** O(N^2) in the worst case. The recursion depth can be O(N), and at each level, we store substrings whose total length can be O(N). The total space for the call stack and stored substrings can reach O(N^2).
**Pros:** Highly efficient and elegant, directly exploiting the recursive structure of the problem.; Guaranteed to find the optimal solution.; Fast enough for the given constraints.
**Cons:** The recursion can lead to high space usage on the call stack for deeply nested strings.; String manipulation (substring, concatenation) can be inefficient in some languages, though acceptable for N=50.
### Explanation
This divide-and-conquer algorithm breaks the problem down into smaller, self-similar subproblems. We define a recursive function that takes a special string `s` and returns its largest possible lexicographical representation.

The function works by first decomposing the input string `s` into its main special components. This is done by scanning the string while keeping track of a balance counter (increment for '1', decrement for '0'). Whenever the balance returns to zero, we have identified a complete special component. For each such component, which will have the form `1M0`, we make a recursive call to find the largest special string for the inner part `M`. After the recursive call returns the optimized middle part, we reconstruct the component by adding the '1' and '0' back. We collect all these optimized components and sort them in reverse lexicographical order. Finally, we concatenate them to produce the answer.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String makeLargestSpecial(String s) {
        // Base case for recursion: an empty string or a string that can't be decomposed.
        if (s.isEmpty()) {
            return "";
        }

        List<String> components = new ArrayList<>();
        int balance = 0;
        int start = 0; // Start index of the current component

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                balance++;
            } else {
                balance--;
            }

            if (balance == 0) {
                // We found a special string component from 'start' to 'i'.
                // This component is of the form 1M0.
                String middle = s.substring(start + 1, i);
                
                // Recursively solve for the middle part.
                String largestMiddle = makeLargestSpecial(middle);
                
                // Reconstruct the component with its largest middle and add to list.
                components.add("1" + largestMiddle + "0");
                
                // Move to the start of the next component.
                start = i + 1;
            }
        }

        // Sort the largest-form components in descending (reverse lexicographical) order.
        Collections.sort(components, Collections.reverseOrder());

        // Join them to form the final result.
        return String.join("", components);
    }
}
```
### Algorithm
1.  The core idea is to use recursion and the principle of divide and conquer.
2.  A special string `S` can be decomposed into a concatenation of primitive special strings: `S = P1P2...Pk`. A primitive special string is one that cannot be broken down into smaller special strings (e.g., `1100` is primitive, but `1010` is not).
3.  The ability to swap consecutive special strings means we can reorder `P1, P2, ..., Pk` in any way we want. To get the lexicographically largest result, we should sort them in descending order.
4.  Each primitive component `Pi` is of the form `1M0`. To maximize `Pi`, we must maximize its inner part `M`. This is a recursive subproblem.
5.  The algorithm is as follows:
    - Create a function `makeLargestSpecial(s)`.
    - Inside the function, iterate through `s` using a balance counter (`+1` for '1', `-1` for '0') to identify the primitive special components.
    - When the balance returns to 0, a component `P` has been found.
    - For each component `P`, extract its middle part `M` (`P = 1M0`).
    - Recursively call `makeLargestSpecial(M)` to get the largest possible version of `M`.
    - Reconstruct the component as `1 + makeLargestSpecial(M) + 0`.
    - Add these maximized components to a list.
    - After finding all components of `s`, sort the list in reverse lexicographical order.
    - Join the sorted components to form the final result.

# Solutions
### Java

```java
class Solution { public String makeLargestSpecial ( String s ) { if ( "" . equals ( s )) { return "" ; } List < String > ans = new ArrayList <>(); int cnt = 0 ; for ( int i = 0 , j = 0 ; i < s . length (); ++ i ) { cnt += s . charAt ( i ) == '1' ? 1 : - 1 ; if ( cnt == 0 ) { String t = "1" + makeLargestSpecial ( s . substring ( j + 1 , i )) + "0" ; ans . add ( t ); j = i + 1 ; } } ans . sort ( Comparator . reverseOrder ()); return String . join ( "" , ans ); } }
```

### CPP

```cpp
class Solution { public: string makeLargestSpecial ( string s ) { if ( s == "" ) return s ; vector < string > ans ; int cnt = 0 ; for ( int i = 0 , j = 0 ; i < s . size (); ++ i ) { cnt += s [ i ] == '1' ? 1 : - 1 ; if ( cnt == 0 ) { ans . push_back ( "1" + makeLargestSpecial ( s . substr ( j + 1 , i - j - 1 )) + "0" ); j = i + 1 ; } } sort ( ans . begin (), ans . end (), greater < string > {}); return accumulate ( ans . begin (), ans . end (), "" s ); } };
```

### Python

```python
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 )
```