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 <= 1000s[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;
}
}
}