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 s.
You can perform the following operation on the string any number of times:
i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'.s[i] to the right until it reaches the end of the string or another '1'. For example, for s = "010010", if we choose i = 1, the resulting string will be s = "000110".Return the maximum number of operations that you can perform.
Example 1:
Input: s = "1001101"
Output: 4
Explanation:
We can perform the following operations:
i = 0. The resulting string is s = "0011101".i = 4. The resulting string is s = "0011011".i = 3. The resulting string is s = "0010111".i = 2. The resulting string is s = "0001111".Example 2:
Input: s = "00111"
Output: 0
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.Problem summary: You are given a binary string s. You can perform the following operation on the string any number of times: Choose any index i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'. Move the character s[i] to the right until it reaches the end of the string or another '1'. For example, for s = "010010", if we choose i = 1, the resulting string will be s = "000110". Return the maximum number of operations that you can perform.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Greedy
"1001101"
"00111"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3228: Maximum Number of Operations to Move Ones to the End
class Solution {
public int maxOperations(String s) {
int ans = 0, cnt = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '1') {
++cnt;
} else if (i > 0 && s.charAt(i - 1) == '1') {
ans += cnt;
}
}
return ans;
}
}
// Accepted solution for LeetCode #3228: Maximum Number of Operations to Move Ones to the End
func maxOperations(s string) (ans int) {
cnt := 0
for i, c := range s {
if c == '1' {
cnt++
} else if i > 0 && s[i-1] == '1' {
ans += cnt
}
}
return
}
# Accepted solution for LeetCode #3228: Maximum Number of Operations to Move Ones to the End
class Solution:
def maxOperations(self, s: str) -> int:
ans = cnt = 0
for i, c in enumerate(s):
if c == "1":
cnt += 1
elif i and s[i - 1] == "1":
ans += cnt
return ans
// Accepted solution for LeetCode #3228: Maximum Number of Operations to Move Ones to the End
impl Solution {
pub fn max_operations(s: String) -> i32 {
let mut ans = 0;
let mut cnt = 0;
let n = s.len();
let bytes = s.as_bytes();
for i in 0..n {
if bytes[i] == b'1' {
cnt += 1;
} else if i > 0 && bytes[i - 1] == b'1' {
ans += cnt;
}
}
ans
}
}
// Accepted solution for LeetCode #3228: Maximum Number of Operations to Move Ones to the End
function maxOperations(s: string): number {
let [ans, cnt] = [0, 0];
const n = s.length;
for (let i = 0; i < n; ++i) {
if (s[i] === '1') {
++cnt;
} else if (i && s[i - 1] === '1') {
ans += cnt;
}
}
return ans;
}
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.