Welcome to Subscribe On Youtube

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

1888. Minimum Number of Flips to Make the Binary String Alternating

Level

Medium

Description

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

• Type-1: Remove the character at the start of the string s and append it to the end of the string.
• Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

• For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Example 1:

Input: s = “111000”

Output: 2

Explanation: Use the first operation two times to make s = “100011”.

Then, use the second operation on the third and sixth elements to make s = “101010”.

Example 2:

Input: s = “010”

Output: 0

Explanation: The string is already alternating.

Example 3:

Input: s = “1110”

Output: 1

Explanation: Use the second operation on the second element to make s = “1010”.

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.

Solution

If only type-2 operations are performed, since the alternating string can either start with 0 or 1, the minimum number of flips can be calculated for the two cases. Use count0 and count1 to represent the minimum number of flips if the alternating string starts with 0 and with 1, respectively.

If the length of s is even, then any type-1 operation will not reduce the number of type-2 operations, so return the minimum of count0 and count1.

If the length of s is odd, then type-1 operations may reduce the number of type-2 operations. For 0 < i < s.length(), we may remove the first i characters at the start of s and append them to the end of s. Before performing type-1 operations, for each 0 < i < s.length(), calculate the minimum number of type-2 operations if s[i - 1] = s[i] = '0' and s[i - 1] = s[i] = '1' respectively. To do this in O(n) time, loop over s forward and backward, and for each 0 <= i < s.length(), calculate the minimum number of type-2 operations needed for both s[i] = 0 and s[i] = 1 in both directions. After the values are calculated, the minimum number of type-2 operations can be calculated.

• Java
• C++
• Python
• TypeScript
• Go

• class Solution {
      public int minFlips(String s) {
          int length = s.length();
          int count0 = 0, count1 = 0;
          for (int i = 0; i < length; i++) {
              char c = s.charAt(i);
              if (c == '0') {
                  if (i % 2 == 0)
                      count1++;
                  else
                      count0++;
              } else {
                  if (i % 2 == 0)
                      count0++;
                  else
                      count1++;
              }
          }
          if (length % 2 == 0)
              return Math.min(count0, count1);
          int[][] dpForward = new int[length][2];
          if (s.charAt(0) == '0')
              dpForward[0][1] = 1;
          else
              dpForward[0][0] = 1;
          for (int i = 1; i < length; i++) {
              if (s.charAt(i) == '0') {
                  dpForward[i][0] = dpForward[i - 1][1];
                  dpForward[i][1] = dpForward[i - 1][0] + 1;
              } else {
                  dpForward[i][0] = dpForward[i - 1][1] + 1;
                  dpForward[i][1] = dpForward[i - 1][0];
              }
          }
          int[][] dpBackward = new int[length][2];
          if (s.charAt(length - 1) == '0')
              dpBackward[length - 1][1] = 1;
          else
              dpBackward[length - 1][0] = 1;
          for (int i = length - 2; i >= 0; i--) {
              if (s.charAt(i) == '0') {
                  dpBackward[i][0] = dpBackward[i + 1][1];
                  dpBackward[i][1] = dpBackward[i + 1][0] + 1;
              } else {
                  dpBackward[i][0] = dpBackward[i + 1][1] + 1;
                  dpBackward[i][1] = dpBackward[i + 1][0];
              }
          }
          int minCount = Math.min(count0, count1);
          for (int i = 1; i < length; i++) {
              int curMin = Math.min(dpForward[i - 1][0] + dpBackward[i][0], dpForward[i - 1][1] + dpBackward[i][1]);
              minCount = Math.min(minCount, curMin);
          }
          return minCount;
      }
  }
  
  ############
  
  class Solution {
      public int minFlips(String s) {
          int n = s.length();
          String target = "01";
          int cnt = 0;
          for (int i = 0; i < n; ++i) {
              cnt += (s.charAt(i) == target.charAt(i & 1) ? 0 : 1);
          }
          int res = Math.min(cnt, n - cnt);
          for (int i = 0; i < n; ++i) {
              cnt -= (s.charAt(i) == target.charAt(i & 1) ? 0 : 1);
              cnt += (s.charAt(i) == target.charAt((i + n) & 1) ? 0 : 1);
              res = Math.min(res, Math.min(cnt, n - cnt));
          }
          return res;
      }
  }
  

• // OJ: https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int minFlips(string s) {
          int N = s.size();
          auto solve = [&](char c) {
              int ans = INT_MAX, cnt = 0;
              for (int i = 0; i < 2 * N; ++i) {
                  cnt += s[i % N] == c ^ (i % 2);
                  if (i - N >= 0) cnt -= s[i - N] == c ^ ((i - N) % 2) ;
                  if (i >= N - 1) ans = min(ans, cnt);
              }
              return ans;
          };
          return min(solve('0'), solve('1'));
      }
  };
  

• class Solution:
      def minFlips(self, s: str) -> int:
          n = len(s)
          target = '01'
          cnt = 0
          for i, c in enumerate(s):
              cnt += c != target[i & 1]
          res = min(cnt, n - cnt)
          for i in range(n):
              cnt -= s[i] != target[i & 1]
              cnt += s[i] != target[(i + n) & 1]
              res = min(res, cnt, n - cnt)
          return res
  
  ############
  
  # 1888. Minimum Number of Flips to Make the Binary String Alternating
  # https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating
  
  class Solution:
      def minFlips(self, s: str) -> int:
          n = len(s)
          s += s
          
          A, B = '', ''
          for i in range(len(s)):
              A += '1' if i % 2 == 0 else '0'
              B += '0' if i % 2 == 0 else '1'
          
          count1 = count2 = 0
          res = float('inf')
          for i in range(len(s)):
              if A[i] != s[i]: count1 += 1
              if B[i] != s[i]: count2 += 1
                  
              if i >= n:
                  if A[i - n] != s[i - n]: count1 -= 1
                  if B[i - n] != s[i - n]: count2 -= 1
              
              if i >= (n - 1):
                  res = min(res, count1, count2)
              
          return res
  
  

• function minFlips(s: string): number {
      const n: number = s.length;
      const target: string[] = ['0', '1'];
      let count: number = 0;
      for (let i: number = 0; i < n; ++i) {
          count += s.charAt(i) == target[i & 1] ? 0 : 1;
      }
      let res = Math.min(count, n - count);
      for (let i: number = 0; i < n; ++i) {
          count -= s.charAt(i) == target[i & 1] ? 0 : 1;
          count += s.charAt(i) == target[(i + n) & 1] ? 0 : 1;
          res = Math.min(res, count, n - count);
      }
      return res;
  }
  
  

• func minFlips(s string) int {
  	n := len(s)
  	target := "01"
  	cnt := 0
  	for i := range s {
  		if s[i] != target[i&1] {
  			cnt++
  		}
  	}
  	ans := min(cnt, n-cnt)
  	for i := range s {
  		if s[i] != target[i&1] {
  			cnt--
  		}
  		if s[i] != target[(i+n)&1] {
  			cnt++
  		}
  		ans = min(ans, min(cnt, n-cnt))
  	}
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions