Ones to the Right

Medium

A shelf holds a row of boxes, some full and some empty. The row is given as a string row of '1' (a full box) and '0' (an empty one). In one move you may swap two **adjacent** boxes. Find the fewest moves after which every empty box is on the left and every full box is on the right.

Example 1

row="0101" → 1

Swap the boxes at indices 1 and 2 to get "0011". One move is enough.

Example 2

row="1100" → 4

Each full box has to get past both empty ones: 2 + 2 = 4 moves.

Example 3

row="000" → 0

Constraints

1 ≤ len(row) ≤ 10⁵
Every character of row is '0' or '1'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Two Pointers String

Similar problems

Pieces Without Shared Letters Medium A Note From Headline Cutouts Medium Greatest Interleave of Two Words Medium Swaps to the k-th Next Arrangement Medium Swapping Brackets Into Balance Medium

Input

row="0101"

Expected

Run checks the first 3 tests in your browser. Submit checks all 155 tests on the server, hidden ones included.