761. Special Binary String¶

• Time: $O(n^2)$
• Space: $O(n)$
  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 class Solution { public: string makeLargestSpecial(string s) { vector specials; int count = 0; for (int i = 0, j = 0; j < s.length(); ++j) { count += s[j] == '1' ? 1 : -1; if (count == 0) { // Find a special string. const string& inner = s.substr(i + 1, j - i - 1); specials.push_back('1' + makeLargestSpecial(inner) + '0'); i = j + 1; } } ranges::sort(specials, greater<>()); return join(specials); } private: string join(const vector& specials) { string joined; for (const string& special : specials) joined += special; return joined; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public String makeLargestSpecial(String s) { List specials = new ArrayList<>(); int count = 0; for (int i = 0, j = 0; j < s.length(); ++j) { count += s.charAt(j) == '1' ? 1 : -1; if (count == 0) { specials.add("1" + makeLargestSpecial(s.substring(i + 1, j)) + "0"); i = j + 1; } } Collections.sort(specials, Collections.reverseOrder()); return String.join("", specials); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def makeLargestSpecial(self, s: str) -> str: specials = [] count = 0 i = 0 for j, c in enumerate(s): count += 1 if c == '1' else -1 if count == 0: specials.append( '1' + self.makeLargestSpecial(s[i + 1:j]) + '0') i = j + 1 return ''.join(sorted(specials)[::-1])