# Maximum Number of Operations to Move Ones to the End
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-operations-to-move-ones-to-the-end)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-operations-to-move-ones-to-the-end
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** String
---
## Problem
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 = "0**001**10"`.

Return the **maximum** number of operations that you can perform.

**Example 1:**

**Input:** s = "1001101"

**Output:** 4

**Explanation:**

We can perform the following operations:

* Choose index `i = 0`. The resulting string is `s = "**001**1101"`.
* Choose index `i = 4`. The resulting string is `s = "0011**01**1"`.
* Choose index `i = 3`. The resulting string is `s = "001**01**11"`.
* Choose index `i = 2`. The resulting string is `s = "00**01**111"`.

**Example 2:**

**Input:** s = "00111"

**Output:** 0

**Constraints:**

* `1 <= s.length <= 105`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It works by repeatedly scanning the string to find a valid operation (`'1'` followed by `'0'`), performing the move, updating the string, and incrementing a counter. This entire process is repeated until no more operations can be performed, i.e., no `'10'` patterns are left in the string.
**Time:** O(K * N), where N is the string length and K is the total number of operations. In the worst-case scenario (e.g., a string like `"11...100...0"`), the number of operations K can be on the order of O(N^2). Each operation involves a scan and modification taking O(N) time. This leads to a very high overall complexity, likely timing out. · **Space:** O(N), where N is the length of the string. This is required to store a mutable copy of the string (e.g., in a `StringBuilder` or `char[]`).
**Pros:** Conceptually simple and directly follows the problem statement.; Easy to implement if performance is not a concern.
**Cons:** Extremely inefficient due to repeated scanning and modification of the string.; The time complexity is very high, making it infeasible for the given constraints (N up to 10^5).; String or character array manipulation in a loop is computationally expensive.
### Explanation
The brute-force method involves a nested loop structure. The outer loop continues as long as we can perform operations, while the inner loop scans the string to find a valid operation to perform.

When we find an index `i` such that `s[i] == '1'` and `s[i+1] == '0'`, we count it as one operation. Then, we must simulate the move of `s[i]`. The '1' at index `i` moves to the right over the block of consecutive '0's starting at `i+1`. To do this in practice, we can use a mutable data structure like a `char[]`. We find the end of the '0' block, shift the block one position to the left, and place the '1' at its new position. 

Because each operation can change the string structure and potentially create new opportunities for operations elsewhere, the simplest way to ensure correctness is to restart the scan from the beginning after each move. The process terminates when a full scan of the string reveals no `'10'` patterns.

```java
class Solution {
    public int maxOperations(String s) {
        StringBuilder sb = new StringBuilder(s);
        int operations = 0;
        boolean changedInPass;

        do {
            changedInPass = false;
            for (int i = 0; i < sb.length() - 1; i++) {
                if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '0') {
                    operations++;
                    changedInPass = true;

                    // Find the end of the consecutive '0's block
                    int j = i + 1;
                    while (j < sb.length() && sb.charAt(j) == '0') {
                        j++;
                    }

                    // Move the '1' at index i to index j-1
                    char one = sb.charAt(i);
                    sb.deleteCharAt(i);
                    sb.insert(j - 1, one);
                    
                    // Restart scan as string has changed
                    break; 
                }
            }
        } while (changedInPass);

        return operations;
    }
}
```
### Algorithm
1. Convert the input string `s` into a mutable character array or `StringBuilder` to allow modifications.
2. Initialize an operation counter `ops` to 0.
3. Use a loop that continues as long as an operation is performed in a pass. A flag, say `op_performed_in_pass`, can be used for this.
4. Inside the loop, iterate through the string from `i = 0` to `s.length() - 2`.
5. If a pattern `s[i] == '1'` and `s[i+1] == '0'` is found:
    a. Increment `ops`.
    b. Set `op_performed_in_pass` to `true`.
    c. Find the end of the consecutive block of '0's that starts at `i+1`. Let this block end at index `j-1`.
    d. Perform the move: shift the characters from `i+1` to `j-1` one position to the left, and place the '1' from index `i` at index `j-1`.
    e. Break the inner loop and restart the scan from the beginning of the now-modified string.
6. If the inner loop completes without finding any `10` pattern (`op_performed_in_pass` remains `false`), exit the outer loop.
7. Return the total `ops`.

## Single Pass with State Counting
A far more efficient approach avoids simulation entirely by making a crucial observation about the nature of the operations. The total number of operations can be determined in a single pass by counting the `1`s and identifying specific trigger points. This method leverages the fact that the total number of operations is fixed regardless of the order in which they are performed.
**Time:** O(N), where N is the length of the string. This is because we perform a single pass through the string. · **Space:** O(1), as we only use a few integer variables to keep track of counts, regardless of the input string size.
**Pros:** Highly efficient with linear time complexity.; Uses constant extra space.; Easily handles the maximum constraints of the problem.
**Cons:** The logic is non-trivial and requires a key insight into the problem's structure, which may not be immediately obvious.
### Explanation
The key insight is that operations are generated at the boundary between a block of `1`s and a subsequent block of `0`s. Consider a structure like `...1110...`. The rightmost `'1'` can move past the `'0'`, which constitutes one operation. After this, the next `'1'` becomes adjacent to the `'0'`'s new position, enabling another operation, and so on. For a block of `k` ones followed by a zero, `k` operations will be generated from this interaction.

We can count this efficiently in one pass. We maintain a running count of `1`s encountered so far (`ones_count`). When we iterate through the string, if we encounter a `'0'` that immediately follows a `'1'` (i.e., `s[i-1] == '1'` and `s[i] == '0'`), we've found a trigger point. At this moment, all the `ones_count` `1`s we've seen so far will eventually have to move past this new block of `0`s. This will contribute `ones_count` to the total number of operations. We add this value to our total and continue the scan. This correctly accumulates the operations generated at each `1-0` interface.

```java
class Solution {
    public int maxOperations(String s) {
        int operations = 0;
        int ones_count = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                ones_count++;
            } else { // s.charAt(i) == '0'
                // An operation is triggered when a '1' is followed by a '0'.
                // This check ensures we only add operations at the start of a '0' block
                // that is preceded by a '1'.
                if (i > 0 && s.charAt(i - 1) == '1') {
                    operations += ones_count;
                }
            }
        }
        return operations;
    }
}
```
### Algorithm
1. Initialize `operations = 0` and `ones_count = 0`.
2. Iterate through the input string `s` with an index `i` from `0` to `s.length() - 1`.
3. If the character `s[i]` is `'1'`:
    a. Increment `ones_count`.
4. If the character `s[i]` is `'0'`:
    a. Check if `i > 0` and the previous character `s[i-1]` was `'1'`. This condition identifies a boundary where a block of `1`s is immediately followed by a block of `0`s.
    b. If the condition is met, it means that each of the `ones_count` `1`s accumulated so far will eventually need to be moved past this block of `0`s. Each such move is initiated by a distinct operation.
    c. Add the current `ones_count` to the `operations` total.
5. After iterating through the entire string, return the final `operations` count.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: int maxOperations ( string s ) { int ans = 0 , cnt = 0 ; int n = s . size (); for ( int i = 0 ; i < n ; ++ i ) { if ( s [ i ] == '1' ) { ++ cnt ; } else if ( i && s [ i - 1 ] == '1' ) { ans += cnt ; } } return ans ; } };
```

### Python

```python
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

```