Question

2938. Separate Black and White Balls

中文文档

Description

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'.

Solutions

Solution 1: Counting Simulation

We consider moving all the '1's to the rightmost side. We use a variable $cnt$ to record the current number of '1's that have been moved to the rightmost side, and a variable $ans$ to record the number of moves.

We traverse the string from right to left. If the current position is '1', then we increment $cnt$ by one, and add $n - i - cnt$ to $ans$, where $n$ is the length of the string. Finally, we return $ans$.

The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.

class Solution:
  def minimumSteps(self, s: str) -> int:
    n = len(s)
    ans = cnt = 0
    for i in range(n - 1, -1, -1):
      if s[i] == '1':
        cnt += 1
        ans += n - i - cnt
    return ans

class Solution {
  public long minimumSteps(String s) {
    long ans = 0;
    int cnt = 0;
    int n = s.length();
    for (int i = n - 1; i >= 0; --i) {
      if (s.charAt(i) == '1') {
        ++cnt;
        ans += n - i - cnt;
      }
    }
    return ans;
  }
}

class Solution {
public:
  long long minimumSteps(string s) {
    long long ans = 0;
    int cnt = 0;
    int n = s.size();
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] == '1') {
        ++cnt;
        ans += n - i - cnt;
      }
    }
    return ans;
  }
};

func minimumSteps(s string) (ans int64) {
  n := len(s)
  cnt := 0
  for i := n - 1; i >= 0; i-- {
    if s[i] == '1' {
      cnt++
      ans += int64(n - i - cnt)
    }
  }
  return
}

function minimumSteps(s: string): number {
  const n = s.length;
  let [ans, cnt] = [0, 0];
  for (let i = n - 1; ~i; --i) {
    if (s[i] === '1') {
      ++cnt;
      ans += n - i - cnt;
    }
  }
  return ans;
}