Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

761. Special Binary String

Time: $O(n\log n) \to O(n^2)$

Space: $O(n)$

			


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




			


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




			


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])