Skip to content

2380. Time Needed to Rearrange a Binary String

Description

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?

Solutions

Solution 1

Thinking

Each second every \(01\) becomes \(10\) at once. \(n \le 1000\) and at most \(n\) rounds, so repeated replacement passes.

Loop \(replace(01,10)\) until none remain; the iteration count is the answer.

1
2
3
4
5
6
7
class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        ans = 0
        while s.count('01'):
            s = s.replace('01', '10')
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func secondsToRemoveOccurrences(s string) int {
    cs := []byte(s)
    ans := 0
    find := true
    for find {
        find = false
        for i := 0; i < len(cs)-1; i++ {
            if cs[i] == '0' && cs[i+1] == '1' {
                cs[i], cs[i+1] = cs[i+1], cs[i]
                i++
                find = true
            }
        }
        if find {
            ans++
        }
    }
    return ans
}

Solution 2

Thinking

Method 1 is quadratic in the worst case. Each \(1\) is moving left through zeros. One scan counts zeros seen: a \(1\) finishes at the max of “one more than the previous \(1\)” and the zero count.

1
2
3
4
5
6
7
8
9
class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        ans = cnt = 0
        for c in s:
            if c == '0':
                cnt += 1
            elif cnt:
                ans = max(ans + 1, cnt)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int ans = 0, cnt = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                ++cnt;
            } else if (cnt > 0) {
                ans = Math.max(ans + 1, cnt);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int ans = 0, cnt = 0;
        for (char c : s) {
            if (c == '0') {
                ++cnt;
            } else if (cnt) {
                ans = max(ans + 1, cnt);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func secondsToRemoveOccurrences(s string) int {
    ans, cnt := 0, 0
    for _, c := range s {
        if c == '0' {
            cnt++
        } else if cnt > 0 {
            ans = max(ans+1, cnt)
        }
    }
    return ans
}

Comments