Maximum Number of Operations to Move Ones to the End

medium string greedy counting

Problem

You are given a binary string s. In one operation you pick an index i with s[i] == '1' and s[i + 1] == '0', then slide that '1' to the right until it hits the end of the string or another '1'. You may repeat this any number of times. Return the maximum number of operations you can perform.

The greedy insight: it is always best to operate on the lowest possible index first. Scanning left to right, keep a count of the '1's seen so far in the current run; every time a run of '1's is followed by a '0', each of those collected '1's contributes one operation.

Inputs = "1001101"

Output4

The two leading 1s each cross the first 0-gap (2 ops), then the three accumulated 1s cross the next 0-gap. Total 4 operations.

s (binary string of 0s and 1s)

def maxOperations(s):
    ans = 0                       # total operations counted
    ones = 0                      # 1s collected in the current run
    for i in range(len(s)):
        if s[i] == '1':
            ones += 1             # another 1 ready to slide right
        elif i > 0 and s[i - 1] == '1':
            ans += ones           # a 1->0 boundary: each 1 moves once
    return ans

function maxOperations(s) {
  let ans = 0;                    // total operations counted
  let ones = 0;                   // 1s collected in the current run
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "1") {
      ones++;                     // another 1 ready to slide right
    } else if (i > 0 && s[i - 1] === "1") {
      ans += ones;                // a 1->0 boundary: each 1 moves once
    }
  }
  return ans;
}

int maxOperations(String s) {
    int ans = 0;                  // total operations counted
    int ones = 0;                 // 1s collected in the current run
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1') {
            ones++;               // another 1 ready to slide right
        } else if (i > 0 && s.charAt(i - 1) == '1') {
            ans += ones;          // a 1->0 boundary: each 1 moves once
        }
    }
    return ans;
}

int maxOperations(string s) {
    int ans = 0;                  // total operations counted
    int ones = 0;                 // 1s collected in the current run
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '1') {
            ones++;               // another 1 ready to slide right
        } else if (i > 0 && s[i - 1] == '1') {
            ans += ones;          // a 1->0 boundary: each 1 moves once
        }
    }
    return ans;
}

Explanation

The operation lets a '1' sitting just before a '0' glide rightward until it stacks against the next '1' (or the end). The hint says to always act on the lowest usable index, and it turns out the total number of operations is independent of the exact order — so we can just count how often a '1' needs to cross a gap of zeros.

Imagine the string as runs of '1's separated by runs of '0's. A run of k ones followed by some zeros: each of those k ones has to traverse that gap, costing k operations, and afterwards those ones merge with whatever ones come later. So the ones accumulate as we move right.

That gives a one-pass count. Walk left to right tracking ones, the number of '1's seen so far in the current contiguous block. When we land on a '0' whose left neighbour is a '1' — the right edge of a block of ones — every collected one will slide across this boundary, so we add ones to the answer.

Crucially we do not reset ones at a gap: those same ones keep moving right and will cross the next gap too, which is exactly why they keep contributing. We only stop adding to ones while we walk over zeros.

Example s = "1001101": the first 1 sets ones = 1; the next 0 follows a 1, so ans += 1. The second 0 follows a 0, no add. Then two 1s push ones to 3; the following 0 adds 3, giving ans = 4. The trailing 1 just raises ones with nothing after it. Answer: 4.

Time: O(n) Space: O(1)