[LeetCode] 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’.

区分黑球与白球。

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

思路

思路是追击型双指针。题目要求我们把所有的黑球（1）都移到右侧，所有白球（0）都移到左侧。同时注意交换的原则，一个黑球移到右侧的前提是同时有一个白球移到左侧，所以一个黑球如果被移动了，那么同时涉及到的白球就不要再重复计算移动次数了。

题目最终的目标是让球形成类似如下这样，0 在左侧，1 在右侧。
000000011111111

具体的做法是从左往右遍历 input 字符串，如果当前遇到的是一个白球（0），那么我要尽可能地把他往左移动。这里我需要两个指针 i 和 j，i 表示的是我当前遍历到的位置，j 表示的是下一个白球可以被移动到的位置。那么在当我遇到某一个白球的时候，这个白球移动的距离 = i - j。每遇到一个白球我就做一次这个动作，并把这个移动的距离累加到结果里。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public long minimumSteps(String s) {
        long res = 0;
		int i = 0;
		int j = 0;
		int n = s.length();
		while (i < n) {
			char cur = s.charAt(i);
			// 遇到白色
			if (cur == '0') {
				res += i - j;
				j++;
			}
			i++;
		}
		return res;
    }
}