Approach #1: Recursion. [Java]
class Solution {
public String makeLargestSpecial(String S) {
int count = 0, i = 0;
List<String> res = new ArrayList<String>();
for (int j = 0; j < S.length(); ++j) {
if (S.charAt(j) == '1') count++;
else count--;
if (count == 0) {
res.add('1' + makeLargestSpecial(S.substring(i+1, j)) + '0');
i = j + 1;
}
}
Collections.sort(res, Collections.reverseOrder());
return String.join("", res);
}
}
Approach #2: DFS. [C++]
class Solution {
public:
string makeLargestSpecial(string S) {
int i = 0;
return dfs(S, i);
}
private:
string dfs(string& s, int& i) {
string res;
vector<string> toks;
while (i < s.size() && res.empty()) {
if (s[i++] == '1') toks.push_back(dfs(s, i));
else res += "1";
}
bool prefix = res.size();
sort(toks.begin(), toks.end());
for (auto it = toks.rbegin(); it != toks.rend(); ++it)
res += *it;
if (prefix) res += '0';
return res;
}
};