1702. Maximum Binary String After Change

You are given a binary string binary consisting of only 0's or 1's. You can apply each of the following operations any number of times:

  • Operation 1: If the number contains the substring "00", you can replace it with "10".
    • For example, "00010" -> "10010"
  • Operation 2: If the number contains the substring "10", you can replace it with "01".
    • For example, "00010" -> "00001"

Return the maximum binary string you can obtain after any number of operations. Binary string x is greater than binary string y if x's decimal representation is greater than y's decimal representation.

 

Example 1:

Input: binary = "000110"
Output: "111011"
Explanation: A valid transformation sequence can be:
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

Example 2:

Input: binary = "01"
Output: "01"
Explanation: "01" cannot be transformed any further.

 

Constraints:

  • 1 <= binary.length <= 105
  • binary consist of '0' and '1'.

Rust Solution

struct Solution;

impl Solution {
    fn maximum_binary_string(binary: String) -> String {
        let binary: Vec<char> = binary.chars().collect();
        let mut res = "".to_string();
        let n = binary.len();
        let mut i = 0;
        while i < n && binary[i] == '1' {
            res.push('1');
            i += 1;
        }
        if i < n {
            let mut m = 0;
            let mut k = 0;
            while i < n {
                if binary[i] == '1' {
                    m += 1;
                }
                k += 1;
                i += 1;
            }
            for _ in 0..k - m - 1 {
                res.push('1');
            }
            res.push('0');
            for _ in 0..m {
                res.push('1');
            }
        }
        res
    }
}

#[test]
fn test() {
    let binary = "000110".to_string();
    let res = "111011".to_string();
    assert_eq!(Solution::maximum_binary_string(binary), res);
    let binary = "01".to_string();
    let res = "01".to_string();
    assert_eq!(Solution::maximum_binary_string(binary), res);
}

Having problems with this solution? Click here to submit an issue on github.