Show problems as
Classic problem #2938MediumTwo PointersStringGreedy

Separate Black and White Balls

Real-world version: Sorting the Drum Rack
Tracked in this browser only
Read Separate Black and White Balls on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A loading rack holds n drums in a row, given as the string s. The character '0' is a light drum and '1' is a heavy drum.

In one move you pick two drums that sit next to each other and exchange their positions.

The rack is safe once every light drum sits somewhere to the left of every heavy drum. Return the smallest number of moves that makes the rack safe.

Examples

Example 1

Input
s = "1100"
Output
4

One route is `1100` -> `1010` -> `1001` -> `0101` -> `0011`, which is four moves and leaves both light drums left of both heavy drums.

Example 2

Input
s = "111000"
Output
9

Each of the three light drums has to travel past each of the three heavy drums, and nine moves reach `000111`.

Example 3

Input
s = "0000"
Output
0

There is no heavy drum at all, so the rack is already safe.

Constraints

  • 1 <= n == s.length <= 10^5
  • s[i] is either '0' or '1'.
  • The answer never exceeds 2.5 * 10^9.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_steps(s: str) -> int:
Java
public long minimumSteps(String s)

More on the same topics