We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Operations to Move Ones to the End

Number: 3493

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

We are given a binary string s. In one operation we may pick any index i where s[i] is '1' and s[i+1] is '0' and “slide” that one to the right – specifically, we remove it from its current place and then “push” it rightward until it either reaches the very end or it is immediately to the left of another ‘1’. Our task is to return the maximum number of operations that we can perform on s.

For example, given s = "1001101" one optimal sequence is:

  1. Pick i = 0. Since s[0]=='1' and next characters are “00” until a ‘1’ is reached, the chosen ‘1’ will jump (in one operation) and be inserted before the first encountered one.
  2. Then pick i = 4 (which now is “1” immediately followed by “0 1”) so that the move only “swaps” the 1 one step.
  3. Next pick i = 3 and finally i = 2 so that each move is done one “step”.

The maximum number of operations in this example is 4.

Key Insights

  • The only allowed operation is applicable on a “10” pattern.
  • Although a 1 might “jump” several zeroes in one operation, if we “delay” moving some ones (by choosing other valid indices) we can force the moves to “unpack” into multiple one‐step moves.
  • In the end the string becomes non‐decreasing (all 0’s followed by all 1’s); thus, an “optimal” strategy can be thought of as moving the ones one step at a time until they are contiguous.
  • A greedy approach (or a “virtual bubble‐sort” view) lets us count the maximum number of “swaps” – that is, the number of times we can “exchange” a 1 and a 0 adjacently – even though an operation might normally “jump” several places.
  • One may derive a mathematical formula using the idea of “assigning” each one a “target” position (so that the ones appear consecutively in the final sorted string) and then count how many one‐step moves can be “simulated” – the trick is that any long jump (performed too early) “bundles” what could have been several operations into one.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)
(Note that while a naive simulation might run in O(n · ops) time, the greedy/counting solution discussed here runs in linear time by “skipping” over many moves.)

Solution

The key is to “delay” moving a 1 as far as possible if it would otherwise jump over several 0’s. One way to understand the problem is to imagine that if we could exchange adjacent “1” and “0” as in bubble‐sort then (by “unpacking” multi‐step jumps into a series of “local” swaps) the maximum number of operations equals the number of adjacent swaps (or inversions) if—and only if—we could guarantee that every swap moved a 1 exactly one place. The allowed operation sometimes “bundles” several adjacent swaps into one move. However, because we are free to choose the order in which we operate, an optimal strategy “delays” some moves so that later the “10” pattern occurs in exactly one‐step increments. A high–level approach is as follows:

  1. Pre–process the string and record the positions (indices) of every ‘1’.
  2. In the final “sorted” state (no adjacent “10” exists) the ones appear consecutively. One may “assign” target positions for the ones (preserving their order). (There is some freedom in where to “anchor” the contiguous block, and a careful “greedy” argument shows that by choosing the moves in the right order the total count of one–step moves is maximized.)
  3. For every 1 that is “behind” where it should be, a one–step move is “charged.” (Any move that would jump more than one space if done immediately is deferred so that eventually the 1 “slides” right by one position at a time.)
  4. Thus the answer is the sum, over every one, of the number of one–step moves that can be “extracted” if the ones are moved as slowly as possible.

An alternative view is to “simulate” the process but – in order not to simulate every individual swap – one uses two pointers (or equivalently a “virtual bubble–sort” idea) to compute how many adjacent “1 0” exchanges can be “unpacked” if the ones “slide” one by one.

Below are code solutions in Python, JavaScript, C++ and Java. (In these implementations we present a simulation version that – although not the most efficient in worst–case – clearly illustrates the greedy strategy. In a real interview you may then explain how to “skip” over many moves and achieve an O(n) counting solution.)

Code Solutions

# Python solution with detailed comments.
def maxOperations(s: str) -> int:
    # Convert string to list for mutable operations.
    arr = list(s)
    n = len(arr)
    
    ops = 0
    made_op = True
    # We simulate until no valid operation exists.
    # In each iteration, we perform one operation at a valid index – choosing the one that moves
    # a '1' only one step if possible.
    while made_op:
        made_op = False
        # We'll scan the string from left to right.
        i = 0
        while i < n - 1:
            # If we encounter the pattern "10":
            if arr[i] == '1' and arr[i+1] == '0':
                # Determine how far the '1' can slide.
                j = i + 1
                # Slide j while in bounds and while we see '0'
                while j < n and arr[j] == '0':
                    j += 1
                # The allowed move is to shift the '1' so that it lands immediately before j,
                # unless j == n then it goes to the end.
                # Note: if j > i+1 this would be a “big jump”. To maximize the number
                # of operations we wish to “unpack” jumps into one-step moves.
                # Therefore, if a one can move just one step (i.e. if j == i+2 or if j==n and i+1==n-1),
                # then we perform the move.
                # Otherwise we skip this occurrence in hopes that a later move will “prepare” a one–step move.
                if j == i+2 or (j == n and i+1 == n-1):
                    # Perform the operation: remove the '1' at index i and insert it at index (j-1)
                    ch = arr.pop(i)
                    # Insertion: j-1 is the index before the encountered '1' (or before the end)
                    arr.insert(j-1, ch)
                    ops += 1
                    made_op = True
                    # After modifying, restart scanning from beginning.
                    break
                else:
                    # If this move would be a multi–step jump, skip it for now.
                    i += 1
            else:
                i += 1
    return ops

# Example usage:
print(maxOperations("1001101"))  # Expected output: 4
print(maxOperations("00111"))    # Expected output: 0
← Back to All Questions