Welcome to Subscribe On Youtube

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

1864. Minimum Number of Swaps to Make the Binary String Alternating

Level

Medium

Description

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

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.

Any two characters may be swapped, even if they are not adjacent.

Example 1:

Input: s = “111000”

Output: 1

Explanation: Swap positions 1 and 4: “111000” -> “101010” The string is now alternating.

Example 2:

Input: s = “010”

Output: 0

Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = “1110”

Output: -1

Constraints:

• 1 <= s.length <= 1000
• s[i] is either '0' or '1'.

Solution

Since swapping cannot change the characters in the string, the number of zeros and ones will not change. So first count the number of zeros and ones in s. If the counts differ by more than 1, return -1.

Otherwise, the alternating string can either start with 0 or 1, or only one of the characters if the length of s is odd. For each possible alternating string, calculate the number of swaps needed, and return the minimum number of swaps.

• Java
• C++
• Python

• class Solution {
      public int minSwaps(String s) {
          int length = s.length();
          int zeros = 0, ones = 0;
          for (int i = 0; i < length; i++) {
              char c = s.charAt(i);
              if (c == '0')
                  zeros++;
              else
                  ones++;
          }
          if (Math.abs(zeros - ones) > 1)
              return -1;
          if (length % 2 == 0) {
              int swap0 = 0, swap1 = 0;
              for (int i = 0; i < length; i++) {
                  char c = s.charAt(i);
                  if (i % 2 == 0) {
                      if (c == '1')
                          swap0++;
                      else
                          swap1++;
                  } else {
                      if (c == '0')
                          swap0++;
                      else
                          swap1++;
                  }
              }
              return Math.min(swap0, swap1) / 2;
          } else {
              int swap = 0;
              if (zeros > ones) {
                  for (int i = 0; i < length; i++) {
                      char c = s.charAt(i);
                      if (i % 2 == 0) {
                          if (c == '1')
                              swap++;
                      } else {
                          if (c == '0')
                              swap++;
                      }
                  }
              } else {
                  for (int i = 0; i < length; i++) {
                      char c = s.charAt(i);
                      if (i % 2 == 0) {
                          if (c == '0')
                              swap++;
                      } else {
                          if (c == '1')
                              swap++;
                      }
                  }
              }
              return swap / 2;
          }
      }
  }
  

• // OJ: https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/
  // Time: O(N)
  // Space: O(N)
  class Solution {
      int solve(string s, int first) {
          int i = 0, j = 1, N = s.size(), ans = 0;
          while (i < N && j < N) {
              while (i < N && s[i] == '0' + first) i += 2;
              while (j < N && s[j] == '0' + 1 - first) j += 2;
              if (i < N && j < N) {
                  swap(s[i], s[j]);
                  ++ans;
              }
          }
          return ans;
      }
  public:
      int minSwaps(string s) {
          int one = 0, zero = 0;
          for (char c : s) {
              if (c == '1') one++;
              else zero++;
          }
          if (zero > one + 1 || one > zero + 1) return -1;
          int ans = INT_MAX;
          if (zero >= one) ans = min(ans, solve(s, 0));
          if (zero <= one) ans = min(ans, solve(s, 1));
          return ans;
      }
  };
  

• class Solution:
      def minSwaps(self, s: str) -> int:
          s0n0 = s0n1 = s1n0 = s1n1 = 0
          for i in range(len(s)):
              if (i & 1) == 0:
                  if s[i] != '0':
                      s0n0 += 1
                  else:
                      s1n1 += 1
              else:
                  if s[i] != '0':
                      s1n0 += 1
                  else:
                      s0n1 += 1
          if s0n0 != s0n1 and s1n0 != s1n1:
              return -1
          if s0n0 != s0n1:
              return s1n0
          if s1n0 != s1n1:
              return s0n0
          return min(s0n0, s1n0)
  
  ############
  
  # 1864. Minimum Number of Swaps to Make the Binary String Alternating
  # https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/
  
  class Solution:
      def minSwaps(self, s: str) -> int:
          counter = collections.Counter(s)
          if abs(counter['1'] - counter['0']) > 1: return -1
          
          n = len(s)
          
          def build(s):
              while len(s) < n:
                  if s[-1] == "0":
                      s += "1"
                  else:
                      s += "0"
              
              return s
          
          res1, res2 = build("0"), build("1")
  
          res = float('inf')
          
          def diff(A):
              return sum(a != b for a,b in zip(s, A))
          
          diff1, diff2 = diff(res1), diff(res2)
  
          if diff1 % 2 == 0:
              res = min(res, diff1)
          if diff2 % 2 == 0:
              res = min(res, diff2)
  
          return res // 2
          
          
          
          
  
  

All Problems

All Solutions