Time Needed to Rearrange a Binary String
Asked at Salesforce
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | MEDIUM | View all Salesforce questions → |
How to Think About It
Simulate the process by scanning for "01" pairs and replacing them in each second.
Recognize that each "1" must move past all "0"s to its left, but only one swap per second per "1".
Count the number of "01" inversions to understand the total work needed.
For each "1", compute how many "0"s are to its left; this determines when it settles.
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.
What Trips People Up in Real Interviews
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).
Solution Code
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
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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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).