<p><strong>Special binary strings</strong> are binary strings with the following two properties:</p>

<ul>
	<li>The number of <code>0</code>&#39;s is equal to the number of <code>1</code>&#39;s.</li>
	<li>Every prefix of the binary string has at least as many <code>1</code>&#39;s as <code>0</code>&#39;s.</li>
</ul>

<p>You are given a <strong>special binary</strong> string <code>s</code>.</p>

<p>A move consists of choosing two consecutive, non-empty, special substrings of <code>s</code>, 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.</p>

<p>Return <em>the lexicographically largest resulting string possible after applying the mentioned operations on the string</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;11011000&quot;
<strong>Output:</strong> &quot;11100100&quot;
<strong>Explanation:</strong> The strings &quot;10&quot; [occuring at s[1]] and &quot;1100&quot; [at s[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;10&quot;
<strong>Output:</strong> &quot;10&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 50</code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>s</code> is a special binary string.</li>
</ul>

typedef long long int ll;

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

        ll n = s.length();
        
        map< ll, vector< pair<ll,ll> > > mp;

        vector<ll> stk;

        function<ll(ll,ll)> getVal = [&]( ll startIdx, int endIdx)->ll {
            ll val = 0;
            for( ll i=startIdx; i<=endIdx; i++) {
                ll d = s[i]-'0';
                val = 2*val + d;
            }
            return val;
        };

        for( ll i=0; i<n; i++) {
            if(s[i]=='1') {
                stk.push_back(i);
            } else {
                mp[stk.size()].push_back({ stk.back(), i});
                stk.pop_back();
            }
        }

        for( auto it=mp.rbegin(); it!=mp.rend(); ++it) {
            
            ll siz = it->first;
            vector< pair<ll,ll> > & intervals = it->second;

            // cout << " siz: " << siz << endl;

            for( ll i=0; i<intervals.size(); i++) {
                ll j = i;
                ll startPos = intervals[i].first;
                while((j+1<intervals.size()) && (intervals[j].second+1==intervals[j+1].first)) {
                    j += 1;
                }
                vector< pair<ll, pair<ll,ll> > > temp;
                for( ll k=i; k<=j; k++) {
                    // cout << " s: " << intervals[k].first << " e: " << intervals[k].second << endl;
                    temp.push_back({ getVal( intervals[k].first, intervals[k].second), intervals[k]});
                }
                sort( temp.begin(), temp.end(), []( const pair<ll, pair<ll,ll> > & pl, const pair<ll, pair<ll,ll> > & pr)->bool {
                    ll nl = pl.second.second - pl.second.first + 1;
                    ll nr = pr.second.second - pr.second.first + 1;
                    return ((pl.first<<nr)^pr.first) > ((pr.first<<nl)^pl.first);
                });
                string t = "";
                for( auto p: temp) {
                    ll m = p.second.second - p.second.first + 1;
                    t.append(s.substr( p.second.first, m));
                }
                for( ll k=0; k<t.length(); k++) {
                    s[startPos+k] = t[k];
                }
                i=j;
            }
            // cout << s << endl;
        }


        return s;
    }
};
8600