[Solved] Time Needed to Rearrange a Binary String LeetCode Contest

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.

Time Needed to Rearrange a Binary String LeetCode Contest

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?

Solution

class Solution 
{
public:
    int secondsToRemoveOccurrences(string s) 
    {
        int cnt=0;
        int fl=1; //flag helps in checking whether any "01" exists or not
        
        while(fl) 
        {
            fl=1;
            for(int i=0; i<s.size(); i++)
            {    
                if(s[i]=='0' && s[i+1]=='1' && i+1<s.size()) //if "01" exists we convert it into "10"
                {
                    swap(s[i], s[i+1]);
                    i++;
                    fl=0;
                }    
            }
            fl = 1-fl; 
            cnt++; //increase time by 1 unit
        }
        return cnt-1;
        
    }
};

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int seconds = 0;
        while (s.indexOf("01") >= 0) {
            s = s.replace("01", "10");
            ++seconds;
        }
        return seconds;
    }
}

class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        cnt = 0
        while ('01' in s):
            s = s.replace('01', '10')
            cnt += 1
        return cnt

Happy Learning – If you require any further information, feel free to contact me.