Maximum Binary String After Change Solution in Java

Problem Description

The “Maximum Binary String After Change” problem involves transforming a binary string (a string made up of 0s and 1s) into the maximum possible binary string by performing specific operations.
For example, starting with the string “100110”, you can change it to “111011” by flipping bits according to the following rules:

Change a ‘0’ to ‘1’ if it’s not the last ‘0’ in the string.
Change a ‘1’ to ‘0’ if it’s the last ‘0’ in the string.

Your goal is to maximize the binary string.

Java Code Solution


class Solution {
  public String maximumBinaryString(String binary) {
    final int zeros = (int) binary.chars().filter(c -> c == '0').count();
    final int prefixOnes = binary.indexOf('0');

    StringBuilder sb = new StringBuilder("1".repeat(binary.length()));

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

Approach Explanation

The approach taken in the code is straightforward. First, we count the number of zeros in the binary string. Then, we find the index of the first ‘0’. After that, we create a new string filled with ‘1’s. If there is at least one ‘0’ in the original string, we replace the last ‘0’ with a ‘0’ at the calculated position. This ensures that we maximize the binary string while adhering to the rules of the operations.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

Real-World Example

Think of this problem like organizing a party. You want to invite as many friends as possible (1s), but you have a few friends (0s) who are hesitant about coming. You can only convince one of them to join the party, and you want to ensure that the party is as lively as possible. By strategically inviting your friends, you can maximize the fun (the binary string)!