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 <= 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; } } } ############ class Solution { public int minSwaps(String s) { int s0n0 = 0, s0n1 = 0; int s1n0 = 0, s1n1 = 0; for (int i = 0; i < s.length(); ++i) { if ((i & 1) == 0) { if (s.charAt(i) != '0') { s0n0 += 1; } else { s1n1 += 1; } } else { if (s.charAt(i) != '0') { s1n0 += 1; } else { s0n1 += 1; } } } if (s0n0 != s0n1 && s1n0 != s1n1) { return -1; } if (s0n0 != s0n1) { return s1n0; } if (s1n0 != s1n1) { return s0n0; } return Math.min(s0n0, s1n0); } } -
// 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 -
/** * @param {string} s * @return {number} */ var minSwaps = function (s) { let n = s.length; let n1 = [...s].reduce((a, c) => parseInt(c) + a, 0); let n0 = n - n1; let count = Infinity; let half = n / 2; // 101、1010 if (n1 == Math.ceil(half) && n0 == Math.floor(half)) { let cur = 0; for (let i = 0; i < n; i++) { if (i % 2 == 0 && s.charAt(i) != '1') cur++; } count = Math.min(count, cur); } // 010、0101 if (n0 == Math.ceil(half) && n1 == Math.floor(half)) { let cur = 0; for (let i = 0; i < n; i++) { if (i % 2 == 0 && s.charAt(i) != '0') cur++; } count = Math.min(count, cur); } return count == Infinity ? -1 : count; };