Time Needed to Rearrange a Binary String

Med

#2166Time: 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.2 companies

Patterns

Dynamic Programming

Data structures

String

Companies

PayPal ServiceNow

Prompt

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 <= 1000
s[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 seconds to 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. A StringBuilder is suitable for this.
Iterate through the current string's characters. If we find a "01" pattern starting at index i, we append "10" to our StringBuilder and 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 of seconds is 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.

1class Solution {2    public int secondsToRemoveOccurrences(String s) {3        int seconds = 0;4        StringBuilder currentS = new StringBuilder(s);5        6        while (true) {7            boolean foundSwap = false;8            int i = 0;9            while (i < currentS.length() - 1) {10                if (currentS.charAt(i) == '0' && currentS.charAt(i + 1) == '1') {11                    foundSwap = true;12                    break;13                }14                i++;15            }16 17            if (!foundSwap) {18                break;19            }20 21            seconds++;22            StringBuilder nextS = new StringBuilder();23            i = 0;24            while (i < currentS.length()) {25                if (i + 1 < currentS.length() && currentS.charAt(i) == '0' && currentS.charAt(i + 1) == '1') {26                    nextS.append("10");27                    i += 2;28                } else {29                    nextS.append(currentS.charAt(i));30                    i++;31                }32            }33            currentS = nextS;34        }35        36        return seconds;37    }38}

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 N is large.
It creates a new string or StringBuilder in every iteration, which can be memory-intensive for very long strings, although within the given constraints it's acceptable.

Instead of a full simulation, we can find the answer in a single pass. The key idea is to analyze the constraints on the time required for the swaps. The total time is determined by the '0' that takes the longest to reach its final sorted position. This time is affected by the number of '1's it needs to pass and the number of other '0's that might be blocking its path. We can formulate a dynamic programming-like relation by iterating through the string and keeping track of the number of '0's seen and the time elapsed so far.

Algorithm

Initialize two integer variables: zeros = 0 to count the number of '0's encountered so far, and seconds = 0 to store the result.
Iterate through the input string s from left to right, character by character.
If the current character is '0', increment the zeros counter.
If the current character is '1':
- Check if zeros > 0. If not, this '1' is already in a sorted position relative to the characters seen so far, so we do nothing.
- If zeros > 0, it means this '1' must move left past all the zeros '0's we've seen. This process takes time. The total time (seconds) is constrained by two factors:
  1. A '0' that was already moving for seconds seconds needs one additional second to pass the current '1'. This implies the new time must be at least seconds + 1.
  2. A contiguous block of zeros '0's needs zeros seconds to fully move past a single '1' (e.g., "001" -> "010" -> "100" takes 2 seconds). This implies the time must be at least zeros.
- To satisfy both constraints, we update seconds = Math.max(seconds + 1, zeros).
After iterating through the entire string, the seconds variable will hold the total time needed.

Walkthrough

We can iterate through the string from left to right, maintaining a count of zeros (zeros) seen so far and the calculated time (seconds). When we encounter a '0', we just increment zeros. When we encounter a '1', if there are any zeros to its left (zeros > 0), we know swaps must occur. The time required for these swaps is determined by the more restrictive of two conditions. First, any '0' that was already part of a seconds-long swap sequence will need one more second to get past this new '1', so the time must be at least seconds + 1. Second, a group of zeros '0's takes zeros seconds to move past a single '1'. Therefore, the updated time must be the maximum of these two values. This single pass correctly accumulates the maximum time required by any '0' to find its final position.

1class Solution {2    public int secondsToRemoveOccurrences(String s) {3        int zeros = 0;4        int seconds = 0;5        for (char c : s.toCharArray()) {6            if (c == '0') {7                zeros++;8            } else if (zeros > 0) {9                // This '1' must be swapped with the '0's on its left.10                // The time is constrained by two factors:11                // 1. A '0' that took `seconds` to get to the position just before this '1'12                //    needs one more second to pass it. Time >= seconds + 1.13                // 2. A block of `zeros` '0's needs `zeros` seconds to pass this '1'.14                //    Time >= zeros.15                // The new time must satisfy both, so we take the maximum.16                seconds = Math.max(seconds + 1, zeros);17            }18        }19        return seconds;20    }21}

Complexity

Time

O(N), where N is the length of the string. This is because we perform a single pass through the string.

Space

O(1), as we only use a few variables (`zeros`, `seconds`) to keep track of the state, regardless of the input string size.

Trade-offs

Pros

Extremely efficient with a linear time complexity.
Uses constant extra space, making it very memory-efficient.

Cons

The logic is more abstract and less intuitive than the direct simulation, requiring a deeper understanding of the underlying process.

Solutions

Solution

1class Solution {2public3  int secondsToRemoveOccurrences(String s) {4    char[] cs = s.toCharArray();5    boolean find = true;6    int ans = 0;7    while (find) {8      find = false;9      for (int i = 0; i < cs.length - 1; ++i) {10        if (cs[i] == '0' && cs[i + 1] == '1') {11          char t = cs[i];12          cs[i] = cs[i + 1];13          cs[i + 1] = t;14          ++i;15          find = true;16        }17      }18      if (find) {19        ++ans;20      }21    }22    return ans;23  }24}

1class Solution {2public:3  int secondsToRemoveOccurrences(string s) {4    bool find = true;5    int ans = 0;6    while (find) {7      find = false;8      for (int i = 0; i < s.size() - 1; ++i) {9        if (s[i] == '0' && s[i + 1] == '1') {10          swap(s[i], s[i + 1]);11          ++i;12          find = true;13        }14      }15      if (find) {16        ++ans;17      }18    }19    return ans;20  }21};

1class Solution:2    def secondsToRemoveOccurrences(self, s: str) -> int: ans = 0 while s . count('01'): s = s . replace('01', '10') ans += 1 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.

← Previous

Previous problem

Next problem