LeetCode 3228 - Maximum Number of Operations to Move Ones to the End

The problem gives us a binary string s, consisting only of characters '0' and '1'. We are allowed to repeatedly perform a specific operation: - Find an index i such that: - s[i] == '1' - s[i + 1] == '0' - Move that '1' to the right until it either: - reaches the end of the…

leetcodemediumstringgreedycounting

LeetCode Problem 3228

Difficulty: 🟡 Medium
Topics: String, Greedy, Counting

Solution

Problem Understanding

The problem gives us a binary string s, consisting only of characters '0' and '1'. We are allowed to repeatedly perform a specific operation:

  • Find an index i such that:

  • s[i] == '1'

  • s[i + 1] == '0'

  • Move that '1' to the right until it either:

  • reaches the end of the string, or

  • stops immediately before another '1'

The goal is to maximize the number of operations we can perform.

The important detail is that each operation moves exactly one '1' across one or more '0' characters. The moved '1' slides as far right as possible before hitting another '1' or the end.

We are not asked to produce the final string. We only need to compute the maximum number of valid operations.

The constraints are important:

  • 1 <= s.length <= 10^5

This immediately tells us that quadratic simulation approaches will likely be too slow. We need an algorithm that runs in linear time, or something very close to it.

A few observations help clarify the behavior:

  • A '1' can only move if it has a '0' immediately to its right.
  • Moving a '1' never changes the relative order of the '1' characters.
  • Every operation effectively moves one '1' past some sequence of zeros.
  • Once all '1' characters are grouped at the end, no more operations are possible.

Some important edge cases include:

  • Strings containing only '0' characters, no operations are possible.
  • Strings containing only '1' characters, no operations are possible.
  • Strings where all zeros already appear before all ones, no operations are possible.
  • Alternating patterns like "101010" can generate many operations.
  • Large inputs require avoiding repeated string reconstruction or repeated scanning.

Approaches

Brute Force Approach

A straightforward approach is to simulate the process exactly as described.

We repeatedly scan the string from left to right looking for a "10" pattern. Whenever we find one, we perform the move operation:

  • Remove the '1'
  • Shift it right until just before the next '1', or the end
  • Count one operation

We continue until no valid "10" pair remains.

This approach is correct because it literally follows the rules of the problem. However, it is inefficient.

Each operation may require rebuilding the string or shifting characters. In the worst case, we may perform O(n) operations, and each operation can cost O(n) time. That leads to an overall complexity of O(n^2).

With n = 10^5, this is too slow.

Optimal Greedy Observation

The key insight is that we do not actually need to simulate movements.

Consider what happens when we encounter a '0' after some number of '1' characters.

Every previously seen '1' can eventually participate in an operation involving this zero.

Suppose we have already seen k ones. When we encounter a zero that has at least one '1' before it, this zero contributes exactly k operations over time.

Why?

Because each preceding '1' can eventually move across this zero in separate operations.

So the problem reduces to:

  • Scan left to right.
  • Maintain how many '1' characters we have seen.
  • Whenever we encounter a '0' after at least one '1', add the current number of ones to the answer.

This gives a clean linear-time greedy solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly simulates string transformations
Optimal O(n) O(1) Counts contributions of zeros using greedy observation

Algorithm Walkthrough

  1. Initialize two variables:
  • ones_seen = 0
  • operations = 0

The variable ones_seen tracks how many '1' characters we have encountered so far. The variable operations stores the total number of operations. 2. Traverse the string from left to right.

We process each character exactly once. 3. If the current character is '1':

  • Increment ones_seen.

This means future zeros can potentially interact with this '1'. 4. If the current character is '0':

  • Add ones_seen to operations.

Every previously encountered '1' can eventually move across this zero in a separate operation. 5. Continue until the entire string has been processed. 6. Return operations.

Why it works

The crucial invariant is that every zero contributes one operation for every '1' that appears before it.

A '1' can only move rightward across zeros. Since the relative order of ones never changes, each pair (previous_one, current_zero) corresponds to exactly one possible future operation.

By summing the number of preceding ones for every zero, we count all operations exactly once.

Python Solution

class Solution:
    def maxOperations(self, s: str) -> int:
        ones_seen = 0
        operations = 0

        for char in s:
            if char == '1':
                ones_seen += 1
            else:
                operations += ones_seen

        return operations

The implementation follows the greedy observation directly.

We maintain ones_seen, which counts how many '1' characters have appeared so far while scanning left to right.

Whenever we encounter a '0', every previous '1' can eventually move across it in a distinct operation. Therefore, we add ones_seen to the total.

Because each character is processed once, the algorithm runs efficiently even for the maximum input size.

Go Solution

func maxOperations(s string) int {
    onesSeen := 0
    operations := 0

    for _, ch := range s {
        if ch == '1' {
            onesSeen++
        } else {
            operations += onesSeen
        }
    }

    return operations
}

The Go implementation mirrors the Python logic closely.

Go strings are immutable byte sequences, but since we only need to read characters sequentially, no special handling is required.

The constraints guarantee that the result fits comfortably within Go's int type.

Worked Examples

Example 1

Input:

s = "1001101"

We track:

  • ones_seen
  • operations
Index Character ones_seen operations Explanation
0 '1' 1 0 First one encountered
1 '0' 1 1 One previous one contributes
2 '0' 1 2 Same one contributes again
3 '1' 2 2 Another one encountered
4 '1' 3 2 Another one encountered
5 '0' 3 5 Three previous ones contribute
6 '1' 4 5 Final one

Final answer:

5

Example 2

Input:

s = "00111"
Index Character ones_seen operations
0 '0' 0 0
1 '0' 0 0
2 '1' 1 0
3 '1' 2 0
4 '1' 3 0

Final answer:

0

No zero appears after a one, so no operations are possible.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(1) Only a few integer variables are used

The algorithm performs a single linear scan of the string. No auxiliary data structures proportional to input size are required.

Test Cases

sol = Solution()

assert sol.maxOperations("1001101") == 5  # mixed pattern
assert sol.maxOperations("00111") == 0  # no movable ones
assert sol.maxOperations("11111") == 0  # all ones
assert sol.maxOperations("00000") == 0  # all zeros
assert sol.maxOperations("10") == 1  # smallest movable case
assert sol.maxOperations("01") == 0  # one already after zero
assert sol.maxOperations("101") == 1  # single operation
assert sol.maxOperations("1010") == 3  # alternating pattern
assert sol.maxOperations("1100") == 4  # every zero interacts with two ones
assert sol.maxOperations("1000") == 3  # one crosses three zeros
assert sol.maxOperations("010101") == 3  # alternating starting with zero
assert sol.maxOperations("111000") == 9  # every one interacts with every zero

Test Summary

Test Why
"1001101" General mixed case
"00111" No valid operations
"11111" All ones
"00000" All zeros
"10" Smallest valid move
"01" No movable one
"101" Single operation scenario
"1010" Alternating structure
"1100" Multiple ones before zeros
"1000" One one crossing many zeros
"010101" Leading zeros
"111000" Maximum pair interactions

Edge Cases

All Ones

Consider a string like "11111".

There are no "10" patterns because every character is already '1'. A naive simulation might unnecessarily attempt transformations, but the optimal solution handles this naturally.

Since no zero appears after a one, operations never increases, so the answer correctly remains 0.

All Zeros

Consider a string like "00000".

No operations are possible because there are no ones to move.

The algorithm handles this correctly because ones_seen always remains 0, so adding it to operations never changes the result.

One Followed by Many Zeros

Consider "1000".

The same '1' can move repeatedly across different zeros. This is an important detail because a naive interpretation might incorrectly assume each one moves only once.

The algorithm correctly counts:

  • first zero contributes 1
  • second zero contributes 1
  • third zero contributes 1

Total operations = 3.

Alternating Pattern

Consider "101010".

This case generates many operations because every zero has multiple preceding ones over time.

The greedy counting approach handles this elegantly by accumulating all preceding ones for each zero, avoiding expensive simulation while still counting every valid operation exactly once.