Algorithm

1. Let $S$ be the input string. First, we observe $S$ is consist of one or more special binary substrings, i.e. $S=S_{1}S_{2}…S_{n}$ where $S_{i}$ is a special binary substring.
2. Now we note that if $S$ only contains one special binary substring, $S[1:-2]$ could contain more special binary substrings.
3. Because we can swap the adjacent special binary substrings, we could just sort $S$ with $S_{i}$ being one single element. However, we also need to ensure that $S_{i}$’s are already preprocessed to be lexicographically largest. This implies a recursive solution. The final solution would be $$S_{\text{sol}}=\texttt{accumulate}(\texttt{sort}(\texttt{sorted}(S_{1}),…,\texttt{sorted}(S_{n})).$$

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F>
recursive(F)->recursive<F>;
auto const rec = [](auto f) { return recursive{std::move(f)}; };

class Solution {
 public:
  string makeLargestSpecial(string S) {

    auto split = [&](string str) -> vector<string> {
      vector<string> result;
      auto go = rec([&](auto&& go, int left, int right, int one, int zero) -> void {
        if (right == size(str))
          return;
        else if (str[right] == '1')
          one++;
        else if (str[right] == '0')
          zero++;

        if (one == zero) {
          result.emplace_back(str.substr(left, right - left + 1));
          go(right + 1, right + 1, one, zero);
        }
        else if (one > zero)
          go(left, right + 1, one, zero);
        else if (one < zero)
          throw std::domain_error("unmatched");
      });
      return (go(0, 0, 0, 0), result);
    };

    auto peel = [&](const string& str) {
      return std::string(begin(str) + 1, end(str) - 1);
    };

    auto solve = rec([&](auto&& solve, vector<string> input) -> std::string {
      if (size(input) == 1)
        return "1" + solve(split(peel(input[0]))) + "0";
      else {
        const auto divided = [&](vector<string> self = {}) {
          std::transform(begin(input), end(input), std::back_inserter(self), [&](const auto& x) {
            return solve(vector<string>{x});
          });
          std::sort(begin(self), end(self), std::greater<>{});
          return self;
        }();
        const auto solution = std::accumulate(begin(divided), end(divided), string{}, [&](const auto& x, const auto& y) {
          return x + y;
        });
        return solution;
      }
    });

    return solve(split(S));
  }
};