What is the optimal solution for the Separate Black and White Balls problem?

The optimal solution uses a two-pointer approach to minimize the number of adjacent swaps needed to group all black balls to the right of the string.

Why is the two-pointer approach used for this problem?

The two-pointer approach efficiently tracks and swaps balls while maintaining a minimal swap count, ensuring a time complexity of O(n).

What is the time complexity of the Separate Black and White Balls problem?

The time complexity is O(n), where n is the length of the string, as the algorithm performs a single scan of the string.

How does GhostInterview help with the Separate Black and White Balls problem?

GhostInterview assists in mastering the two-pointer technique, helping identify pitfalls and practice optimizing the solution with minimal swaps.

What is the key observation for solving the Separate Black and White Balls problem?

The key observation is that every 1 in the string should be swapped with every 0 on its right side, which can be efficiently tracked using two pointers.

#2938

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

区分黑球与白球

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。给你一个长度为 n 、下标从 0 开始的二进制字符串 s ，其中 1 和 0 分别代表黑色和白色的球。在每一步中，你可以选择两个相邻的球并交换它们。返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的最小步数」。示例 1：输入： …

双指针字符串贪心

题目描述

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

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

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

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

示例 1：

输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。

示例 2：

输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2 。

示例 3：

输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧。

提示：

1 <= n == s.length <= 10⁵
s[i] 不是 '0'，就是 '1'。

lightbulb

解题思路

方法一：计数模拟

我们考虑将所有的 $1$ 移到最右边，用一个变量 $cnt$ 记录当前已经移动到最右边的 $1$ 的个数，用一个变量 $ans$ 记录移动的次数。

我们从右往左遍历字符串，如果当前位置是 $1$ ，那么我们将 $cnt$ 加一，同时将 $n - i - cnt$ 加到 $ans$ 中，其中 $n$ 是字符串的长度。最后返回 $ans$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate demonstrate efficient two-pointer usage for optimizing adjacent swap operations?
question_mark
How well does the candidate recognize and utilize the greedy nature of the problem?
question_mark
Does the candidate consider edge cases, such as when all black balls are already grouped?

warning

常见陷阱

外企场景

error
Failing to track the correct number of swaps or not considering the distance each black ball needs to move.
error
Overcomplicating the solution by using nested loops or unnecessary operations.
error
Not understanding the two-pointer method and relying on less efficient approaches.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string was larger, close to the upper limit of 100,000? How would the solution scale?
arrow_right_alt
What if the balls were not just two colors but had more varieties? How would the solution need to adapt?
arrow_right_alt
What if the problem asked to group black balls to the left instead of the right?

help

常见问题

外企场景

继续练习

#2697 字典序最小回文串 #3302 字典序最小的合法序列 #2486 追加字符以获得子序列