README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/1800-1899/1864.Minimum%20Number%20of%20Swaps%20to%20Make%20the%20Binary%20String%20Alternating/README_EN.md	1600	Weekly Contest 241 Q2	Greedy String

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

中文文档

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'.

Solutions

Solution 1

Python3

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)

Java

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);
    }
}

JavaScript

/**
 * @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;
};