Time Needed to Rearrange a Binary String
MedPrompt
You are given a binary string s. In one second, all occurrences of "01" are simultaneously replaced with "10". This process repeats until no occurrences of "01" exist.
Return the number of seconds needed to complete this process.
Example 1:
Input: s = "0110101"
Output: 4
Explanation:
After one second, s becomes "1011010".
After another second, s becomes "1101100".
After the third second, s becomes "1110100".
After the fourth second, s becomes "1111000".
No occurrence of "01" exists any longer, and the process needed 4 seconds to complete,
so we return 4.Example 2:
Input: s = "11100"
Output: 0
Explanation:
No occurrence of "01" exists in s, and the processes needed 0 seconds to complete,
so we return 0.
Constraints:
1 <= s.length <= 1000s[i]is either'0'or'1'.
Follow up:
Can you solve this problem in O(n) time complexity?
Approaches
2 approaches with complexity analysis and trade-offs.
The most intuitive way to solve this problem is to directly simulate the process described. We can model the passage of time with a loop, where each iteration represents one second. In each second, we scan the string and identify all occurrences of "01". We then replace them with "10" to produce the string's state for the next second. This process is repeated until no "01" substrings exist in the string. The total number of iterations will be the answer.
Algorithm
- Initialize a counter
secondsto 0. - Start a loop that continues as long as the string contains the substring
"01". - Inside the loop, increment
seconds. - To handle the simultaneous replacement of all
"01"occurrences, we must build a new version of the string in each iteration. AStringBuilderis suitable for this. - Iterate through the current string's characters. If we find a
"01"pattern starting at indexi, we append"10"to ourStringBuilderand advance our loop counter by 2. - Otherwise, we append the current character and advance by 1.
- After iterating through the entire string, we update our main string to this new version.
- The loop terminates when a full pass over the string finds no
"01"substrings. The value ofsecondsis the result.
Walkthrough
To implement this, we can use a while loop that continues as long as swaps are being made. Inside the loop, we count a second and then construct the next state of the string. A crucial detail is that all swaps happen simultaneously. This means we must base our swaps on the string's state at the beginning of the second. A simple way to achieve this is to build a new string (or StringBuilder) for the next state, rather than modifying the string in-place. We iterate through the current string, and whenever we see a "01", we append "10" to our new string. Otherwise, we append the character we are currently at. After the pass is complete, we update the current string to the new one we just built. If a pass completes with no swaps made, we have reached the final state and can stop.
class Solution { public int secondsToRemoveOccurrences(String s) { int seconds = 0; StringBuilder currentS = new StringBuilder(s); while (true) { boolean foundSwap = false; int i = 0; while (i < currentS.length() - 1) { if (currentS.charAt(i) == '0' && currentS.charAt(i + 1) == '1') { foundSwap = true; break; } i++; } if (!foundSwap) { break; } seconds++; StringBuilder nextS = new StringBuilder(); i = 0; while (i < currentS.length()) { if (i + 1 < currentS.length() && currentS.charAt(i) == '0' && currentS.charAt(i + 1) == '1') { nextS.append("10"); i += 2; } else { nextS.append(currentS.charAt(i)); i++; } } currentS = nextS; } return seconds; }}Complexity
Time
O(N * T), where N is the length of the string and T is the total number of seconds required. In the worst-case scenario, like the string `"011...1"`, a single '0' has to move N-1 positions, taking one second per position. Thus, T can be up to O(N), making the total time complexity O(N^2).
Space
O(N), where N is the length of the string. This is because in each iteration of the simulation, we create a new `StringBuilder` or string of length N to store the state of the string for the next second.
Trade-offs
Pros
The logic is straightforward and easy to implement as it directly follows the problem statement.
It is guaranteed to be correct.
Cons
The time complexity of O(N^2) can be too slow if the input string length
Nis large.It creates a new string or
StringBuilderin every iteration, which can be memory-intensive for very long strings, although within the given constraints it's acceptable.
Solutions
Solution
class Solution {public int secondsToRemoveOccurrences(String s) { char[] cs = s.toCharArray(); boolean find = true; int ans = 0; while (find) { find = false; for (int i = 0; i < cs.length - 1; ++i) { if (cs[i] == '0' && cs[i + 1] == '1') { char t = cs[i]; cs[i] = cs[i + 1]; cs[i + 1] = t; ++i; find = true; } } if (find) { ++ans; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.