Welcome to Subscribe On Youtube

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: Direct Implementation

Since the data range of this question is not large, it can be simulated violently. In each round, all “01” in the string will be replaced with “10”, and the statistical rounds will be used as the answer.

Time complexity $O(n^2)$. The time complexity of each round is $O(n)$, and at most $n$ rounds of operations are performed.

Solution 2

The question is to replace all “01” strings with “10”, which actually moves all “1”s to the left. After the operation, the left side is all “1” and the right side is all “0”.

If we want to rearrange “0100010” to “1100000”, two situations will occur:

1. If there are $cnt$ “0”s to the left of a “1”, then it takes $cnt$ seconds to move the “1” to the leftmost position;
2. If there are consecutive “1”s, moving the two “1”s to the leftmost position requires an additional $1$ seconds.

Look at the example below:

Time (seconds)	Example 1	Example 2
0	0001	00011
1	0010	00101
2	0100	01010
3	1000	10100
4	-	11000

We can see that if there is only one “1” after $cnt$ “0”s, then it only takes $cnt$ seconds, if there are consecutive “1”s, it takes additional $1$ seconds.

So for every “1” in the string, we compute $ans=max(ans+1, cnt)$.

Time complexity $O(n)$, space complexity $O(1)$.

• Java
• C++
• Python
• Go

• 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;
      }
  }
  
  
  // Solution 2
  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;
      }
  }
  
  

• 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;
      }
  };
  
  
  // Solution 2
  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;
      }
  };
  
  

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

• 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
  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
  }
  
  

All Problems

All Solutions