Time Need To Rearrange Binary String

https://leetcode.com/problems/time-needed-to-rearrange-a-binary-string/description/

🚀 O(n) Challenge: Can You Explain This Solution?

Given a binary string s, in one second all occurrences of "01" are simultaneously replaced with "10".

Return the number of seconds needed until no "01" remains.

Example

Input:  "0110101"

Second 1: 1011010
Second 2: 1101100
Second 3: 1110100
Second 4: 1111000

Output: 4

Optimal O(n) Solution

class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int zeros = 0;
        int time = 0;

        for (char ch : s) {
            if (ch == '0') {
                zeros++;
            }
            else if (zeros > 0) {
                time = max(time + 1, zeros);
            }
        }

        return time;
    }
};

Questions for Discussion 🤔

1. What does the variable zeros represent?
2. Why do we only update time when we encounter a '1'?
3. Why is the transition:

time = max(time + 1, zeros);

instead of simply:

time = zeros;

1. What does time + 1 signify?
2. Can you explain why this works in O(n) without actually simulating each second?

💬 Interested to see different explanations and intuitions for this elegant solution. The max(time + 1, zeros) transition is particularly interesting! 🔥

Understanding the O(n) Solution

The key observation is:

• Every '1' needs to move left across all zeros that appear before it.
• If there are zeros zeros before a '1', then that '1' needs at least zeros seconds to reach its final position.
• However, multiple '1's can block each other because a '1' can move at most one position per second.

Consider:

0110101

Processing left to right:

Answer = 4

Why max(time + 1, zeros)?

When we encounter a '1':

Case 1: Enough zeros before it

0001

This 1 must cross 3 zeros.

time = zeros = 3

Case 2: Previous 1s are blocking

011

The second 1 cannot overtake the first one.

Even if it only needs to cross one zero, it must wait for the previous 1.

time = time + 1

Hence:

time = max(time + 1, zeros);