# Minimum Number of Swaps to Make the Binary String Alternating
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Societe Generale](https://scaleengineer.com/companies/societe-generale)
---
## Problem
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'`.

# Approaches
## Two-Pass Counting Method
This approach first validates if an alternating string can be formed by checking the counts of '0's and '1's. If possible, it then calculates the number of swaps required for each potential alternating pattern ('0101...' and/or '1010...') by counting misplaced characters in separate passes. Finally, it returns the minimum number of swaps required.
**Time:** O(N), where N is the length of the string. The string is traversed a constant number of times. · **Space:** O(1), as we only use a few variables to store counts, regardless of the input string size.
**Pros:** The logic is straightforward, separating the validation step from the calculation step.; Achieves optimal asymptotic time and space complexity.
**Cons:** It requires multiple passes over the input string, which is slightly less performant than a single-pass solution due to loop overhead.
### Explanation
An alternating binary string can only have two forms: one starting with '0' (e.g., "0101...") and one starting with '1' (e.g., "1010...").

First, we check if it's possible to form an alternating string. We count the number of zeros (`zeros`) and ones (`ones`).
- If the length `n` is even, `zeros` must equal `ones`.
- If `n` is odd, `abs(zeros - ones)` must be 1.
If these conditions are not met, it's impossible, so we return -1.

If possible, we determine the target(s). The key insight is that the minimum number of swaps to convert a string into an anagram of itself is the number of misplaced elements of one type. For example, to achieve the target `0101...`, we need to swap every '1' currently at an even position with a '0' at an odd position. The number of such '1's at even positions is exactly the number of swaps required.

This leads to a two-pass algorithm:
1.  **Pass 1:** Count the total number of '0's and '1's to validate possibility.
2.  **Pass 2:** Based on the valid target(s), count the misplaced characters to determine the number of swaps. For an even length string, this pass might be run twice (once for each potential target) to find the minimum.

```java
class Solution {
    public int minSwaps(String s) {
        int n = s.length();
        int ones = 0, zeros = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                ones++;
            } else {
                zeros++;
            }
        }

        if (Math.abs(ones - zeros) > 1) {
            return -1;
        }

        if (n % 2 == 0) {
            if (ones != zeros) return -1;
            // For even length, both targets are possible. Calculate swaps for both and take min.
            int swapsFor0Start = countMisplacedForTarget(s, '0');
            int swapsFor1Start = countMisplacedForTarget(s, '1');
            return Math.min(swapsFor0Start, swapsFor1Start);
        } else {
            // For odd length, only one target is possible.
            if (ones > zeros) {
                // Target must start with '1' ("1010...")
                return countMisplacedForTarget(s, '1');
            } else {
                // Target must start with '0' ("0101...")
                return countMisplacedForTarget(s, '0');
            }
        }
    }

    // Counts swaps for a target starting with `startChar`.
    // This is the number of `otherChar`s at even positions.
    private int countMisplacedForTarget(String s, char startChar) {
        int misplacedCount = 0;
        char otherChar = (startChar == '0' ? '1' : '0');
        // Even positions should have startChar. We count how many have the otherChar.
        for (int i = 0; i < s.length(); i += 2) {
            if (s.charAt(i) == otherChar) {
                misplacedCount++;
            }
        }
        return misplacedCount;
    }
}
```
### Algorithm
1.  First, iterate through the string to count the number of zeros (`zeros`) and ones (`ones`).
2.  Check if it's possible to form an alternating string. Let `n` be the string length.
    - An alternating string is impossible if the difference between the count of zeros and ones is greater than 1 (`abs(zeros - ones) > 1`). In this case, return -1.
3.  If `n` is even, the counts must be equal (`zeros == ones`). If not, it's also impossible (this is covered by the previous check).
4.  Determine the target alternating string(s) and calculate the minimum swaps for each.
    - A helper function, `countSwaps(startChar)`, can be used. This function calculates the number of swaps needed to transform the string into an alternating one starting with `startChar`.
    - The number of swaps is equal to the number of characters that are in the wrong type of position. For a target starting with '0' (`0101...`), the '0's should be at even indices and '1's at odd indices. The number of swaps is the count of '1's at even positions. Similarly, for a target starting with '1', swaps are the count of '0's at even positions.
5.  Handle the cases based on the length `n`:
    - If `n` is even, two targets are possible (`0101...` and `1010...`). Calculate the swaps for both and return the minimum.
    - If `n` is odd, only one target is possible. If `zeros > ones`, the target must start with '0'. If `ones > zeros`, the target must start with '1'. Calculate and return the swaps for that single target.

## Optimized Single-Pass Counting
This approach optimizes the counting method by gathering all necessary information—total counts of '0's and '1's, and the number of misplaced characters for both potential alternating patterns—in a single pass through the input string. This avoids redundant iterations and makes the implementation more compact and efficient.
**Time:** O(N), where N is the length of the string, as it involves a single pass. · **Space:** O(1), as only a constant number of variables are used for counting.
**Pros:** Most efficient implementation, as it traverses the string only once.; Reduces constant factors and overhead associated with multiple loops.; Achieves optimal time and space complexity.
**Cons:** The logic within the single loop is slightly more complex, as it tracks multiple counts simultaneously.
### Explanation
Instead of making separate passes, we can count everything at once. We iterate through the string a single time, keeping track of the total number of '1's, as well as the number of swaps needed for both the '0'-starting and '1'-starting alternating patterns.

The number of swaps for a target starting with '0' (`0101...`) is the number of '1's at even positions. The number of swaps for a target starting with '1' (`1010...`) is the number of '0's at even positions. We can count both of these during our single traversal.

After the loop, we have all the necessary counts. We first check if a solution is possible using the total counts of '0's and '1's. If it is, we use the pre-calculated swap counts to return the answer based on the string's length, just as in the previous approach.

```java
class Solution {
    public int minSwaps(String s) {
        int n = s.length();
        int ones = 0;
        int misplaced_for_0_start = 0; // Counts '1's at even positions
        int misplaced_for_1_start = 0; // Counts '0's at even positions

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '1') {
                ones++;
            }
            if (i % 2 == 0) { // Check characters at even positions
                if (c == '1') {
                    misplaced_for_0_start++;
                } else { // c == '0'
                    misplaced_for_1_start++;
                }
            }
        }

        int zeros = n - ones;
        if (Math.abs(ones - zeros) > 1) {
            return -1;
        }

        if (n % 2 == 0) {
            // For even length, both targets are possible.
            // The number of misplaced '1's at even positions must equal misplaced '0's at even positions for the two targets.
            return Math.min(misplaced_for_0_start, misplaced_for_1_start);
        } else {
            // For odd length, only one target is possible.
            if (ones > zeros) { // Target must start with '1'
                return misplaced_for_1_start;
            } else { // Target must start with '0'
                return misplaced_for_0_start;
            }
        }
    }
}
```
### Algorithm
1.  Initialize counters: `ones = 0`, `misplaced_for_0_start = 0`, and `misplaced_for_1_start = 0`.
2.  Iterate through the string `s` with index `i` from 0 to `n-1` in a single pass.
3.  Inside the loop:
    - Increment `ones` if `s[i]` is '1'.
    - Check the character at the current index `i` against the two possible alternating patterns.
    - If `i` is an even position:
        - If `s[i]` is '1', it's a misplaced character for a target starting with '0'. Increment `misplaced_for_0_start`.
        - If `s[i]` is '0', it's a misplaced character for a target starting with '1'. Increment `misplaced_for_1_start`.
4.  After the loop, calculate `zeros = n - ones`.
5.  Check for impossibility: if `abs(ones - zeros) > 1`, return -1.
6.  Determine the result based on `n`'s parity:
    - If `n` is even, return `min(misplaced_for_0_start, misplaced_for_1_start)`.
    - If `n` is odd:
        - If `ones > zeros`, the target must start with '1'. Return `misplaced_for_1_start`.
        - Else, the target must start with '0'. Return `misplaced_for_0_start`.

# Solutions
### Java

```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

```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 ; 
```

### CPP

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

```

### Python

```python
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)

```