Question

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

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

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

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

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

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

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) {
    int ans = 0, cnt = 0;
    for (char c : s) {
      if (c == '0') {
        ++cnt;
      } else if (cnt) {
        ans = max(ans + 1, cnt);
      }
    }
    return ans;
  }
};

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
}