Using greedy without proof
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Move from brute-force thinking to an efficient approach using greedy strategy.
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:
"00", you can replace it with "10".
"00010" -> "10010""10", you can replace it with "01".
"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 <= 105binary consist of '0' and '1'.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Greedy
"000110"
"01"
longest-binary-subsequence-less-than-or-equal-to-k)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1702: Maximum Binary String After Change
class Solution {
public String maximumBinaryString(String binary) {
int k = binary.indexOf('0');
if (k == -1) {
return binary;
}
int n = binary.length();
for (int i = k + 1; i < n; ++i) {
if (binary.charAt(i) == '0') {
++k;
}
}
char[] ans = binary.toCharArray();
Arrays.fill(ans, '1');
ans[k] = '0';
return String.valueOf(ans);
}
}
// Accepted solution for LeetCode #1702: Maximum Binary String After Change
func maximumBinaryString(binary string) string {
k := strings.IndexByte(binary, '0')
if k == -1 {
return binary
}
for _, c := range binary[k+1:] {
if c == '0' {
k++
}
}
ans := []byte(binary)
for i := range ans {
ans[i] = '1'
}
ans[k] = '0'
return string(ans)
}
# Accepted solution for LeetCode #1702: Maximum Binary String After Change
class Solution:
def maximumBinaryString(self, binary: str) -> str:
k = binary.find('0')
if k == -1:
return binary
k += binary[k + 1 :].count('0')
return '1' * k + '0' + '1' * (len(binary) - k - 1)
// Accepted solution for LeetCode #1702: Maximum Binary String After Change
impl Solution {
pub fn maximum_binary_string(binary: String) -> String {
if let Some(k) = binary.find('0') {
let k = k + binary[k + 1..].chars().filter(|&c| c == '0').count();
return format!(
"{}{}{}",
"1".repeat(k),
"0",
"1".repeat(binary.len() - k - 1)
);
}
binary
}
}
// Accepted solution for LeetCode #1702: Maximum Binary String After Change
function maximumBinaryString(binary: string): string {
let k = binary.indexOf('0');
if (k === -1) {
return binary;
}
k += binary.slice(k + 1).split('0').length - 1;
return '1'.repeat(k) + '0' + '1'.repeat(binary.length - k - 1);
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.