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

SourceWeekly Contest 241 Q2DifficultyMediumRating1600

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: Counting

Thinking

We may swap bits to reach \(0101\ldots\) or \(1010\ldots\). The two targets demand different \(0/1\) counts, so a mismatch of more than one is impossible.

Compare \(n_0\) and \(n_1\): if they differ by more than \(1\), return \(-1\); if equal, try both starting bits; otherwise start with the majority bit. Each swap fixes two mismatches, so the answer is half the number of wrong positions.

First, we count the number of characters \(0\) and \(1\) in the string \(\textit{s}\), denoted as \(n_0\) and \(n_1\) respectively.

If the absolute difference between \(n_0\) and \(n_1\) is greater than \(1\), it is impossible to form an alternating string, so we return \(-1\).

If \(n_0\) and \(n_1\) are equal, we can calculate the number of swaps needed to convert the string into an alternating string starting with \(0\) and starting with \(1\), and take the minimum value.

If \(n_0\) and \(n_1\) are not equal, we only need to calculate the number of swaps needed to convert the string into an alternating string starting with the character that appears more frequently.

The problem is reduced to calculating the number of swaps needed to convert the string \(\textit{s}\) into an alternating string starting with character \(c\).

We define a function \(\text{calc}(c)\), which represents the number of swaps needed to convert the string \(\textit{s}\) into an alternating string starting with character \(c\). We traverse the string \(\textit{s}\), and for each position \(i\), if the parity of \(i\) is different from \(c\), we need to swap the character at this position, incrementing the counter by \(1\). Since each swap makes two positions have the same character, the final number of swaps is half of the counter.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(\textit{s}\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def minSwaps(self, s: str) -> int:
        def calc(c: int) -> int:
            return sum((c ^ i & 1) != x for i, x in enumerate(map(int, s))) // 2

        n0 = s.count("0")
        n1 = len(s) - n0
        if abs(n0 - n1) > 1:
            return -1
        if n0 == n1:
            return min(calc(0), calc(1))
        return calc(0 if n0 > n1 else 1)

class Solution {
    private char[] s;

    public int minSwaps(String s) {
        this.s = s.toCharArray();
        int n1 = 0;
        for (char c : this.s) {
            n1 += (c - '0');
        }
        int n0 = this.s.length - n1;
        if (Math.abs(n0 - n1) > 1) {
            return -1;
        }
        if (n0 == n1) {
            return Math.min(calc(0), calc(1));
        }
        return calc(n0 > n1 ? 0 : 1);
    }

    private int calc(int c) {
        int cnt = 0;
        for (int i = 0; i < s.length; ++i) {
            int x = s[i] - '0';
            if ((i & 1 ^ c) != x) {
                ++cnt;
            }
        }
        return cnt / 2;
    }
}

class Solution {
public:
    int minSwaps(string s) {
        int n0 = ranges::count(s, '0');
        int n1 = s.size() - n0;
        if (abs(n0 - n1) > 1) {
            return -1;
        }
        auto calc = [&](int c) -> int {
            int cnt = 0;
            for (int i = 0; i < s.size(); ++i) {
                int x = s[i] - '0';
                if ((i & 1 ^ c) != x) {
                    ++cnt;
                }
            }
            return cnt / 2;
        };
        if (n0 == n1) {
            return min(calc(0), calc(1));
        }
        return calc(n0 > n1 ? 0 : 1);
    }
};

func minSwaps(s string) int {
    n0 := strings.Count(s, "0")
    n1 := len(s) - n0
    if abs(n0-n1) > 1 {
        return -1
    }
    calc := func(c int) int {
        cnt := 0
        for i, ch := range s {
            x := int(ch - '0')
            if i&1^c != x {
                cnt++
            }
        }
        return cnt / 2
    }
    if n0 == n1 {
        return min(calc(0), calc(1))
    }
    if n0 > n1 {
        return calc(0)
    }
    return calc(1)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

function minSwaps(s: string): number {
    const n0 = (s.match(/0/g) || []).length;
    const n1 = s.length - n0;
    if (Math.abs(n0 - n1) > 1) {
        return -1;
    }
    const calc = (c: number): number => {
        let cnt = 0;
        for (let i = 0; i < s.length; i++) {
            const x = +s[i];
            if (((i & 1) ^ c) !== x) {
                cnt++;
            }
        }
        return Math.floor(cnt / 2);
    };
    if (n0 === n1) {
        return Math.min(calc(0), calc(1));
    }
    return calc(n0 > n1 ? 0 : 1);
}

/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function (s) {
    const n0 = (s.match(/0/g) || []).length;
    const n1 = s.length - n0;
    if (Math.abs(n0 - n1) > 1) {
        return -1;
    }
    const calc = c => {
        let cnt = 0;
        for (let i = 0; i < s.length; i++) {
            const x = +s[i];
            if (((i & 1) ^ c) !== x) {
                cnt++;
            }
        }
        return Math.floor(cnt / 2);
    };
    if (n0 === n1) {
        return Math.min(calc(0), calc(1));
    }
    return calc(n0 > n1 ? 0 : 1);
};

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

Description

Solutions

Solution 1: Counting

Comments