Time Needed to Rearrange a Binary String — Solution
Time Needed to Rearrange a Binary String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Time Needed to Rearrange a Binary String is a medium coding problem on strings, dynamic programming and simulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a binary string s. Every second, all occurrences of the substring "01" are replaced by "10" at the same time. The process repeats until s contains no "01" at all.
Return the number of seconds the process takes.
Example 1
Input: s = "0011"
Output: 3
Explanation: `0011` → `0101` → `1010` → `1100`.
Example 2
Input: s = "1001"
Output: 2
Explanation: `1001` → `1010` → `1100`.
Example 3
Input: s = "1100"
Output: 0
Explanation: There is no `"01"` to begin with.
Constraints
1 <= s.length <= 1000s[i] is either '0' or '1'
Follow-up: Can you solve it in O(n) time?
Hints for Time Needed to Rearrange a Binary String
Hint 1
In the end every
1sits to the left of every0. Each second, a1with a0directly to its left moves one step left.Hint 2
A
1needs at least as many seconds as there are0s before it — it must pass each of them.Hint 3
It may also be blocked by the
1in front of it, finishing at least one second after that one. Sweep left to right:ans = max(ans + 1, zeros)at each1that has a0before it.
How to solve Time Needed to Rearrange a Binary String
Track when each 1 finishes moving. A 1 with z zeros before it needs at least z seconds, and it finishes at least one second after the previous moving 1, which can block it.
Approach
- Sweep
sfrom left to right, countingzeros, the0s seen so far, and keepingans, the finishing time of the last1that had to move. - On a
0, increasezeros. - On a
1withzeros > 0, setans = max(ans + 1, zeros). A1with no0before it never moves and changes nothing. - Return
ans.
Why it works
Each second a moving 1 advances one place unless the 1 directly ahead of it is still sitting in its way. If it is never blocked it finishes after exactly zeros seconds. If it catches up with the previous moving 1, it from then on trails it by one second, finishing at previous + 1. Its true finishing time is the larger of these two bounds, and the last 1 to finish determines the whole process.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Leading
1s do not move; do not let them bumpans. - Simulating directly costs O(n²) — acceptable for n = 1000, but the sweep is linear.
- Replacements happen simultaneously, so a
1moves at most one place per second.
Reference solution
Python
def secondsToRemoveOccurrences(s: str) -> int:
zeros = 0
ans = 0
for ch in s:
if ch == "0":
zeros += 1
elif zeros > 0:
ans = max(ans + 1, zeros)
return ansJava
public static int secondsToRemoveOccurrences(String s) {
int zeros = 0, ans = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '0') zeros++;
else if (zeros > 0) ans = Math.max(ans + 1, zeros);
}
return ans;
}C++
int secondsToRemoveOccurrences(string s) {
int zeros = 0, ans = 0;
for (char ch : s) {
if (ch == '0') zeros++;
else if (zeros > 0) ans = max(ans + 1, zeros);
}
return ans;
}JavaScript
var secondsToRemoveOccurrences = function(s) {
var zeros = 0, ans = 0;
for (var i = 0; i < s.length; i++) {
if (s[i] === "0") zeros++;
else if (zeros > 0) ans = Math.max(ans + 1, zeros);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming