Skip to content

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<string> 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;
      }
    }

    sort(begin(specials), end(specials), greater<>());
    return join(specials);
  }

 private:
  string join(const vector<string>& 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<String> 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])