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

All Problems

All Solutions