Code Implementation

class Solution:
    def minSwaps(self, s: str) -> int:
        n = len(s)
        ones = s.count('1')
        zeros = n - ones

        if abs(ones - zeros) > 1:
            return -1

        # Helper to count mismatches for a given starting char
        def count_swaps(start_with):
            swaps = 0
            for i, c in enumerate(s):
                expected = str((i + start_with) % 2)
                if c != expected:
                    swaps += 1
            return swaps // 2

        if ones > zeros:
            return count_swaps(1)
        elif zeros > ones:
            return count_swaps(0)
        else:
            return min(count_swaps(0), count_swaps(1))
      

class Solution {
public:
    int minSwaps(string s) {
        int n = s.size();
        int ones = count(s.begin(), s.end(), '1');
        int zeros = n - ones;
        if (abs(ones - zeros) > 1) return -1;

        auto count_swaps = [&](int start_with) {
            int swaps = 0;
            for (int i = 0; i < n; ++i) {
                char expected = ((i + start_with) % 2) + '0';
                if (s[i] != expected) swaps++;
            }
            return swaps / 2;
        };

        if (ones > zeros) return count_swaps(1);
        else if (zeros > ones) return count_swaps(0);
        else return min(count_swaps(0), count_swaps(1));
    }
};
      

class Solution {
    public int minSwaps(String s) {
        int n = s.length();
        int ones = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') ones++;
        }
        int zeros = n - ones;
        if (Math.abs(ones - zeros) > 1) return -1;

        int swaps0 = 0, swaps1 = 0;
        for (int i = 0; i < n; ++i) {
            char expected0 = (char)('0' + (i % 2));
            char expected1 = (char)('0' + ((i + 1) % 2));
            if (s.charAt(i) != expected0) swaps0++;
            if (s.charAt(i) != expected1) swaps1++;
        }
        if (ones > zeros) return swaps1 / 2;
        else if (zeros > ones) return swaps0 / 2;
        else return Math.min(swaps0, swaps1) / 2;
    }
}
      

var minSwaps = function(s) {
    let n = s.length;
    let ones = 0;
    for (let c of s) if (c === '1') ones++;
    let zeros = n - ones;
    if (Math.abs(ones - zeros) > 1) return -1;

    function countSwaps(startWith) {
        let swaps = 0;
        for (let i = 0; i < n; ++i) {
            let expected = ((i + startWith) % 2).toString();
            if (s[i] !== expected) swaps++;
        }
        return Math.floor(swaps / 2);
    }

    if (ones > zeros) return countSwaps(1);
    else if (zeros > ones) return countSwaps(0);
    else return Math.min(countSwaps(0), countSwaps(1));
};
      

Problem Description

Given a binary string s (a string containing only '0' and '1'), your task is to determine the minimum number of swaps needed to make s alternate between '0' and '1'. Alternating means no two adjacent characters are the same, so valid results look like "0101..." or "1010...". Each swap can exchange any two characters (not necessarily adjacent). If it is impossible to make s alternating, return -1.

• Each character of s can be used only once per swap.
• Swaps can be between any two indices.
• The answer is the minimum number of swaps required.
• If no solution exists, return -1.

Thought Process

At first glance, it might seem you need to try all possible swaps, but that would be very inefficient. Instead, start by thinking about what makes a binary string alternating: the characters at even and odd positions must always differ. That means, for a string of length n, the counts of '0's and '1's must be almost equal (the difference can be at most 1). If not, it's impossible.

Next, consider two possible alternating patterns:

• Pattern A: starts with '0' (i.e., "010101...")
• Pattern B: starts with '1' (i.e., "101010...")

The brute-force approach of generating all permutations is not feasible for large strings, so we look for a pattern-based, counting solution.

Solution Approach

• Step 1: Count '0's and '1's.
  • If the difference between the count of '0's and '1's is more than 1, return -1 (impossible).
• Step 2: Consider both alternating patterns.
  • Pattern A (start with '0'): positions at even indices should be '0', odd indices '1'.
  • Pattern B (start with '1'): positions at even indices should be '1', odd indices '0'.
• Step 3: Count mismatches for each pattern.
  • For each index, check if s[i] matches the expected character for that pattern. If not, increment the mismatch count.
• Step 4: Compute swaps.
  • Each swap fixes two mismatches, so swaps needed is mismatches // 2.
  • If the counts of '0's and '1's are equal, both patterns are possible: pick the one needing fewer swaps.
  • If there are more '1's, only the pattern starting with '1' is possible; if more '0's, only the pattern starting with '0' is possible.
• Step 5: Return the minimum swaps, or -1 if not possible.

This approach is efficient because it avoids trying all permutations and instead leverages the properties of alternating binary strings and counting mismatches.

Example Walkthrough

Let's walk through an example with s = "111000":

1. Count '1's: 3, Count '0's: 3 (difference is 0, so possible).
2. Try pattern starting with '0' ("010101"):
   • Indices: 0 1 2 3 4 5
   • Pattern: 0 1 0 1 0 1
   • String: 1 1 1 0 0 0
   • Compare each index:
     • Index 0: expected '0', got '1' (mismatch)
     • Index 1: expected '1', got '1' (match)
     • Index 2: expected '0', got '1' (mismatch)
     • Index 3: expected '1', got '0' (mismatch)
     • Index 4: expected '0', got '0' (match)
     • Index 5: expected '1', got '0' (mismatch)
   • Total mismatches: 4. Swaps needed: 4 // 2 = 2.
3. Try pattern starting with '1' ("101010"):
   • Compare each index:
     • Index 0: expected '1', got '1' (match)
     • Index 1: expected '0', got '1' (mismatch)
     • Index 2: expected '1', got '1' (match)
     • Index 3: expected '0', got '0' (match)
     • Index 4: expected '1', got '0' (mismatch)
     • Index 5: expected '0', got '0' (match)
   • Total mismatches: 2. Swaps needed: 2 // 2 = 1.
4. Both patterns are valid, but starting with '1' requires fewer swaps. So the answer is 1.

Time and Space Complexity

• Brute-force approach:
  • Would involve generating all permutations or all possible swaps, which is factorial time: O(n!).
  • Space would also be very high due to storing permutations.
• Optimized approach (counting mismatches):
  • Time Complexity: O(n) — We scan the string a constant number of times: once for counting, and once for checking mismatches.
  • Space Complexity: O(1) — Only a few integer counters are used, no extra data structures proportional to input size.

Summary

The key insight is that an alternating binary string must have nearly equal numbers of '0's and '1's, and that each swap can fix two mismatches. By comparing the input string to both possible alternating patterns, we can efficiently count mismatches and compute the minimum number of swaps needed. This avoids brute-force and results in an O(n) solution that is both elegant and efficient.