Welcome to Subscribe On Youtube
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 0indexed 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 <= 10^{5}
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 { 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; } };

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

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