Scale Engineer

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
GreedyCounting
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 <= 105
  • 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

  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.

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.

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

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.

Solutions

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

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 →

Next problem