#2938
Separate Black and White Balls
specialist · 650 · lc medium +30 · verified · 64% accepted · 878 likes · top 67%
Description
A binary string s of length n represents n balls on a table: '1' for black and '0' for white.
Each step, you can swap two adjacent balls.
Determine the minimum number of swaps to arrange all white balls on the left and all black balls on the right.
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.
Code
1
2
3