Maximum Number of Operations to Move Ones to the End

Med

#2867Time: 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[]`).

Patterns

Greedy Counting

Data structures

String

Prompt

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.

Example 1:

Input: s = "1001101"

Output: 4

Explanation:

We can perform the following operations:

Choose index i = 0. The resulting string is s = "0011101".
Choose index i = 4. The resulting string is s = "0011011".
Choose index i = 3. The resulting string is s = "0010111".
Choose index i = 2. The resulting string is s = "0001111".

Example 2:

Input: s = "00111"

Output: 0

Constraints:

1 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Convert the input string s into a mutable character array or StringBuilder to allow modifications.
Initialize an operation counter ops to 0.
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.
Inside the loop, iterate through the string from i = 0 to s.length() - 2.
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.
If the inner loop completes without finding any 10 pattern (op_performed_in_pass remains false), exit the outer loop.
Return the total ops.

Walkthrough

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.

1class Solution {2    public int maxOperations(String s) {3        StringBuilder sb = new StringBuilder(s);4        int operations = 0;5        boolean changedInPass;6 7        do {8            changedInPass = false;9            for (int i = 0; i < sb.length() - 1; i++) {10                if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '0') {11                    operations++;12                    changedInPass = true;13 14                    // Find the end of the consecutive '0's block15                    int j = i + 1;16                    while (j < sb.length() && sb.charAt(j) == '0') {17                        j++;18                    }19 20                    // Move the '1' at index i to index j-121                    char one = sb.charAt(i);22                    sb.deleteCharAt(i);23                    sb.insert(j - 1, one);24                    25                    // Restart scan as string has changed26                    break; 27                }28            }29        } while (changedInPass);30 31        return operations;32    }33}

Complexity

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[]`).

Trade-offs

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.

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 1s 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.

Algorithm

Initialize operations = 0 and ones_count = 0.
Iterate through the input string s with an index i from 0 to s.length() - 1.
If the character s[i] is '1': a. Increment ones_count.
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 1s is immediately followed by a block of 0s. b. If the condition is met, it means that each of the ones_count 1s accumulated so far will eventually need to be moved past this block of 0s. Each such move is initiated by a distinct operation. c. Add the current ones_count to the operations total.
After iterating through the entire string, return the final operations count.

Walkthrough

The key insight is that operations are generated at the boundary between a block of 1s and a subsequent block of 0s. 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 1s 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 1s we've seen so far will eventually have to move past this new block of 0s. 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.

1class Solution {2    public int maxOperations(String s) {3        int operations = 0;4        int ones_count = 0;5        int n = s.length();6 7        for (int i = 0; i < n; i++) {8            if (s.charAt(i) == '1') {9                ones_count++;10            } else { // s.charAt(i) == '0'11                // An operation is triggered when a '1' is followed by a '0'.12                // This check ensures we only add operations at the start of a '0' block13                // that is preceded by a '1'.14                if (i > 0 && s.charAt(i - 1) == '1') {15                    operations += ones_count;16                }17            }18        }19        return operations;20    }21}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem