Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2380.html

2380. Time Needed to Rearrange a Binary String

• Difficulty: Medium.
• Related Topics: String, Dynamic Programming, Simulation.
• Similar Questions: Minimum Swaps to Group All 1’s Together, Minimum Swaps to Group All 1’s Together II.

Problem

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?

Solution (Java, C++, Python)

• Java
• Python
• C++
• Go

• class Solution {
      public int secondsToRemoveOccurrences(String s) {
          int lastOne = -1;
          int result = 0;
          int prevResult = 0;
          int curResult = 0;
          int countOne = 0;
          int countZero = 0;
          int diff;
          int pTarget;
          int pWait;
          int cTarget;
          for (int i = 0; i < s.length(); ++i) {
              if (s.charAt(i) == '0') {
                  ++countZero;
                  continue;
              }
              ++countOne;
              diff = i - lastOne - 1;
              prevResult = curResult;
              cTarget = countOne - 1;
              pTarget = cTarget - 1;
              pWait = prevResult - (lastOne - pTarget);
              if (diff > pWait) {
                  curResult = countZero;
              } else {
                  curResult = countZero == 0 ? 0 : pWait - diff + 1 + countZero;
              }
              result = curResult;
              lastOne = i;
          }
          return result;
      }
  }
  
  ############
  
  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:
      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
  
  ############
  
  # 2380. Time Needed to Rearrange a Binary String
  # https://leetcode.com/problems/time-needed-to-rearrange-a-binary-string
  
  class Solution:
      def secondsToRemoveOccurrences(self, s: str) -> int:
          n = len(s)
          res = 0
          
          while "01" in s:
              s = s.replace("01", "10")
              res += 1
          
          return res
  
  

• 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
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions