##### 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

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.

• 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