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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Operations to Move Ones to the End

Difficulty: Medium

Problem Description

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'. Return the maximum number of operations that you can perform.

Key Insights

  • The operation can only be performed on a '1' followed by a '0'.
  • Each '1' can potentially be moved past multiple '0's.
  • The total number of operations is determined by the number of '1's and the number of '0's that can follow them.
  • The maximum number of operations is equal to the count of '1's multiplied by the number of available '0's to the right of each '1'.

Space and Time Complexity

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

Solution

To solve this problem, we can use a greedy approach by iterating through the string while keeping track of:

  1. The count of '1's encountered so far.
  2. The count of '0's that can be moved to the right of '1's.

As we traverse the string:

  • Each time we encounter a '1', we increment the count of '1's.
  • Each time we encounter a '0', we can think of it as a potential target for the '1's that come before it. We increment the count of '0's.

The maximum number of operations is the total count of '1's multiplied by the total count of '0's that follow them.

Code Solutions

def maxOperations(s: str) -> int:
    count_ones = 0  # Count of '1's
    count_zeros = 0  # Count of '0's
    operations = 0  # Total operations

    for char in s:
        if char == '1':
            count_ones += 1  # Increment count of '1's
            operations += count_zeros  # Add available '0's for each '1'
        else:
            count_zeros += 1  # Increment count of '0's

    return operations  # Return the total number of operations
← Back to All Questions