Skip to content

1702. Maximum Binary String After Change 👍

  • Time: $O(n)$
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  string maximumBinaryString(string binary) {
    //     e.g. binary = "100110"
    // Do Operation 2 -> "100011"
    // Do Operation 1 -> "111011"
    // So, the index of the only '0' is prefixOnes + zeros - 1.
    const int zeros = count(binary.begin(), binary.end(), '0');
    const int prefixOnes = binary.find('0');

    // Make the entire string as 1s.
    binary.assign(binary.length(), '1');

    // Make the only '0' if necessary.
    if (prefixOnes != string::npos)
      binary[prefixOnes + zeros - 1] = '0';
    return binary;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public String maximumBinaryString(String binary) {
    //     e.g. binary = "100110"
    // Do Operation 2 -> "100011"
    // Do Operation 1 -> "111011"
    // So, the index of the only '0' is prefixOnes + zeros - 1.
    final int zeros = (int) binary.chars().filter(c -> c == '0').count();
    final int prefixOnes = binary.indexOf('0');

    // Make the entire String as 1s.
    StringBuilder sb = new StringBuilder("1".repeat(binary.length()));

    // Make the only '0' if necessary.
    if (prefixOnes != -1)
      sb.setCharAt(prefixOnes + zeros - 1, '0');
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maximumBinaryString(self, binary: str) -> str:
    #     e.g. binary = '100110'
    # Do Operation 2 -> '100011'
    # Do Operation 1 -> '111011'
    # So, the index of the only '0' is prefixOnes + zeros - 1.
    zeros = binary.count('0')
    prefixOnes = binary.find('0')

    # Make the entire string as 1s.
    ans = ['1'] * len(binary)

    # Make the only '0' if necessary.
    if prefixOnes != -1:
      ans[prefixOnes + zeros - 1] = '0'
    return ''.join(ans)