Problem

Given a binary string s, return _theminimum 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.

Examples

Example 1

1
2
3
4

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "1 _1_ 10 _0_ 0" -> "1 _0_ 10 _1_ 0"
The string is now alternating.

Example 2

1
2
3

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3

1
2

Input: s = "1110"
Output: -1

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'.

Solution

Method 1 – Greedy Counting and Mismatch Swaps

Intuition

To make the string alternating, we need to match the counts of ‘0’s and ‘1’s for possible patterns (starting with ‘0’ or ‘1’). For each pattern, count mismatches and compute swaps needed. If impossible, return -1.

Approach

  1. Count the number of ‘0’s and ‘1’s in the string.
  2. If the difference in counts is more than 1, it’s impossible.
  3. Try both patterns: starting with ‘0’ and starting with ‘1’.
  4. For each pattern, count mismatches (positions where s[i] != expected).
  5. The minimum swaps is half the number of mismatches for a valid pattern.
  6. Return the minimum swaps or -1 if impossible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <string>
using namespace std;
class Solution {
public:
    int minSwaps(string s) {
        int c0 = 0, c1 = 0;
        for (char ch : s) (ch == '0' ? c0 : c1)++;
        if (abs(c0 - c1) > 1) return -1;
        int m1 = 0, m2 = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != (i % 2 ? '1' : '0')) m1++;
            if (s[i] != (i % 2 ? '0' : '1')) m2++;
        }
        int res = 1e9;
        if (c0 >= c1) res = min(res, m1 / 2);
        if (c1 >= c0) res = min(res, m2 / 2);
        return res == 1e9 ? -1 : res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func minSwaps(s string) int {
    c0, c1 := 0, 0
    for _, ch := range s {
        if ch == '0' {
            c0++
        } else {
            c1++
        }
    }
    if abs(c0-c1) > 1 {
        return -1
    }
    m1, m2 := 0, 0
    for i := 0; i < len(s); i++ {
        if s[i] != byte('0'+i%2) {
            m1++
        }
        if s[i] != byte('1'-i%2) {
            m2++
        }
    }
    res := 1 << 30
    if c0 >= c1 {
        res = min(res, m1/2)
    }
    if c1 >= c0 {
        res = min(res, m2/2)
    }
    if res == 1<<30 {
        return -1
    }
    return res
}
func min(a, b int) int { if a < b { return a } else { return b } }
func abs(x int) int { if x < 0 { return -x } else { return x } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minSwaps(String s) {
        int c0 = 0, c1 = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '0') c0++;
            else c1++;
        }
        if (Math.abs(c0 - c1) > 1) return -1;
        int m1 = 0, m2 = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != (i % 2 == 0 ? '0' : '1')) m1++;
            if (s.charAt(i) != (i % 2 == 0 ? '1' : '0')) m2++;
        }
        int res = Integer.MAX_VALUE;
        if (c0 >= c1) res = Math.min(res, m1 / 2);
        if (c1 >= c0) res = Math.min(res, m2 / 2);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minSwaps(s: String): Int {
        var c0 = 0; var c1 = 0
        for (ch in s) if (ch == '0') c0++ else c1++
        if (kotlin.math.abs(c0 - c1) > 1) return -1
        var m1 = 0; var m2 = 0
        for (i in s.indices) {
            if (s[i] != if (i % 2 == 0) '0' else '1') m1++
            if (s[i] != if (i % 2 == 0) '1' else '0') m2++
        }
        var res = Int.MAX_VALUE
        if (c0 >= c1) res = minOf(res, m1 / 2)
        if (c1 >= c0) res = minOf(res, m2 / 2)
        return if (res == Int.MAX_VALUE) -1 else res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minSwaps(self, s: str) -> int:
        c0, c1 = s.count('0'), s.count('1')
        if abs(c0 - c1) > 1:
            return -1
        m1 = sum(s[i] != str(i % 2) for i in range(len(s)))
        m2 = sum(s[i] != str(1 - i % 2) for i in range(len(s)))
        res = float('inf')
        if c0 >= c1:
            res = min(res, m1 // 2)
        if c1 >= c0:
            res = min(res, m2 // 2)
        return -1 if res == float('inf') else res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn min_swaps(s: String) -> i32 {
        let c0 = s.chars().filter(|&c| c == '0').count() as i32;
        let c1 = s.chars().filter(|&c| c == '1').count() as i32;
        if (c0 - c1).abs() > 1 { return -1; }
        let m1 = s.chars().enumerate().filter(|(i, c)| *c != if i % 2 == 0 { '0' } else { '1' }).count() as i32;
        let m2 = s.chars().enumerate().filter(|(i, c)| *c != if i % 2 == 0 { '1' } else { '0' }).count() as i32;
        let mut res = i32::MAX;
        if c0 >= c1 { res = res.min(m1 / 2); }
        if c1 >= c0 { res = res.min(m2 / 2); }
        if res == i32::MAX { -1 } else { res }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    minSwaps(s: string): number {
        const c0 = [...s].filter(c => c === '0').length;
        const c1 = [...s].filter(c => c === '1').length;
        if (Math.abs(c0 - c1) > 1) return -1;
        let m1 = 0, m2 = 0;
        for (let i = 0; i < s.length; ++i) {
            if (s[i] !== (i % 2 === 0 ? '0' : '1')) m1++;
            if (s[i] !== (i % 2 === 0 ? '1' : '0')) m2++;
        }
        let res = Infinity;
        if (c0 >= c1) res = Math.min(res, Math.floor(m1 / 2));
        if (c1 >= c0) res = Math.min(res, Math.floor(m2 / 2));
        return res === Infinity ? -1 : res;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of s, single pass for counts and mismatches.
  • 🧺 Space complexity: O(1) — constant extra space.