MediumStringDynamic ProgrammingSimulationUpdated Sep 2026

2380. Time Needed to Rearrange a Binary String

Asked at Salesforce

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

String

Companies

1

Problem

You are given a binary string s made only of '0' and '1' characters.

Every second, all occurrences of the pattern "01" are replaced by "10" at the same time. This means a '1' can move one step to the left per second, but only if the spot directly to its left is a '0' at the start of that second. The process keeps going until no "01" pair is left anywhere in the string.

Return the number of seconds needed until the string stops changing. If there is no "01" at the start, the answer is 0.

The key rule that changes the answer: swaps happen simultaneously, not one at a time. So two '1's cannot both use the same second to pass the same '0', and a '1' that is blocked behind another '1' has to wait.

All "01" pairs swap in the same second

s01101010123456The three "01" pairs at positions (0,1), (3,4) and (5,6)all swap in second 1.after 1s10110100123456The result is "1011010"; new "01" pairs appear and thenext second starts.
In one second every "01" becomes "10" at the same time, and the process repeats until no "01" is left.

Constraints

  • ●1 <= s.length <= 1000
  • ●s[i] is either '0' or '1'

Examples

Example 1
Inputs = "0110101"
Output4
WhyThe string changes as "0110101" → "1011010" → "1101100" → "1110100" → "1111000". After the fourth second there is no "01" left, so the answer is 4.
Example 2
Inputs = "11100"
Output0
WhyAll the '1's are already on the left and all the '0's on the right, so there is no "01" anywhere. Nothing happens, so 0 seconds are needed.
Example 3
Inputs = "0101"
Output2
WhySecond 1: both "01" pairs swap at once, giving "1010". Second 2: the middle "01" swaps, giving "1100". Now no "01" remains, so the answer is 2.

Asked At

1 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →

How to Think About It

1

Simulate the process by scanning for "01" pairs and replacing them in each second.

2

Recognize that each "1" must move past all "0"s to its left, but only one swap per second per "1".

3

Count the number of "01" inversions to understand the total work needed.

4

For each "1", compute how many "0"s are to its left; this determines when it settles.

5

The answer is the maximum over all "1"s of (number of "0"s to the left) + (its index among "1"s).

Optimal Approach

Traverse the string and track two values: the count of "0"s seen so far and the current time for each "1". For each "1" encountered at position i with c zeros to its left, the time for this "1" to settle is c + index, where index is which "1" this is (0-indexed). The answer is the maximum such value. This works because in each second, all "01" pairs swap simultaneously, so the k-th "1" can swap at most once per second while the (k-1)-th "1" ahead of it also moves.

Count zeros to the left, plus which '1' this is

s011010101234561st '1'2nd '1'3rd '1'4th '1'Walk left to right; zeros counts '0's seen so far,one_index counts '1's seen so far.time for each '1''1' #zeros leftone_indextotal1st1012nd1123rd2244th336The 3rd '1' has 2 zeros to its left and 2 '1's ahead ofit, so it finishes at second 4 — the maximum.time = zeros_so_far + one_indexans = max(ans, time)answer = 4
Each '1' needs (zeros before it) seconds to pass them, and it must also wait its turn behind earlier '1's.
ComplexityTime O(n)Space O(1)One left-to-right pass over the string, keeping only two counters, so the cost is linear in the length of s.

What Trips People Up in Real Interviews

1

Clarify whether replacement happens simultaneously or sequentially within one second (simultaneously).

2

Think about what "01" means: it is a "0" immediately followed by a "1" in the string at any position.

3

A brute-force simulation is O(n^2) and may be too slow for large strings.

4

The key insight is that each "1" needs a number of swaps equal to the number of "0"s to its left, but they can move in parallel.

5

The total time is determined by the "1" that takes the longest, which is the maximum over all "1"s of (zeros_left + index_of_1_among_ones).

Solution Code

O(n) time
class Solution:
    def rearrangeCharacters(self, s: str) -> int:
        zeros = 0
        one_index = 0
        ans = 0
        for ch in s:
            if ch == '0':
                zeros += 1
            else:
                ans = max(ans, zeros + one_index)
                one_index += 1
        return ans

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Time Needed to Rearrange a Binary String problem?

Given a binary string s consisting only of characters "0" and "1", in one second, every occurrence of "01" is replaced with "10". This process repeats until no more "01" subsequences exist. Return the number of seconds needed to reach this state.

How do you solve Time Needed to Rearrange a Binary String?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Time Needed to Rearrange a Binary String?

Time Needed to Rearrange a Binary String is asked at Salesforce. It is a medium difficulty problem.

What are common mistakes on Time Needed to Rearrange a Binary String?
  • Clarify whether replacement happens simultaneously or sequentially within one second (simultaneously).
  • Think about what "01" means: it is a "0" immediately followed by a "1" in the string at any position.
  • A brute-force simulation is O(n^2) and may be too slow for large strings.
  • The key insight is that each "1" needs a number of swaps equal to the number of "0"s to its left, but they can move in parallel.
  • The total time is determined by the "1" that takes the longest, which is the maximum over all "1"s of (zeros_left + index_of_1_among_ones).