2938. Separate Black and White Balls

There are n balls on a table, each ball has a color black or white.

You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.

In each step, you can choose two adjacent balls and swap them.

Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

Example 1:

Input: s = "101"
Output: 1
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "011".
Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.

Example 2:

Input: s = "100"
Output: 2
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "010".
- Swap s[1] and s[2], s = "001".
It can be proven that the minimum number of steps needed is 2.

Example 3:

Input: s = "0111"
Output: 0
Explanation: All the black balls are already grouped to the right.

Constraints:

• 1 <= n == s.length <= 105
• s[i] is either '0' or '1'.

Approach 01

class Solution {
public:
    long long minimumSteps(string binaryString) {
        long totalSteps = 0;
        int countOnes = 0;

        for (const char currentChar : binaryString) {
            if (currentChar == '1') {
                ++countOnes;
            } else { // Move 1s to the front of the current '0'.
                totalSteps += countOnes;
            }
        }

        return totalSteps;
    }
};

class Solution:
    def minimumSteps(self, binaryString: str) -> int:
        totalSteps = 0
        countOnes = 0

        for currentChar in binaryString:
            if currentChar == '1':
                countOnes += 1
            else:  # Move 1s to the front of the current '0'.
                totalSteps += countOnes

        return totalSteps

Time Complexity

• Single pass through the string:

  The algorithm iterates through the binary string of length n exactly once. For each character, we perform constant time operations (incrementing counters and adding to the total steps). Therefore, the time complexity for the loop is \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the length of the input binary string.

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of extra space for variables like totalSteps and countOnes. There are no additional data structures that grow with the input size.

• Overall Space Complexity:

  The space complexity is \(O(1)\), meaning it uses constant space regardless of the size of the input string.