Minimum number of swaps to make the binary string alternating

String Greedy

43.9% acceptance

Feb 25, 2026

624

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_swaps(s: String) -> i32 {
    let ones = s.bytes().filter(|&b| b == b'1').count() as i32;
    let zeros = s.len() as i32 - ones;
    let diff = (ones - zeros).abs();
    if diff > 1 {
      return -1;
    }

    // Count mismatches for pattern starting with '1' (1010...) and '0' (0101...)
    let count_mismatches = |start: u8| -> i32 {
      s.bytes().enumerate()
        .filter(|&(i, b)| {
          let expected = if i % 2 == 0 { start } else { b'1' - start + b'0' };
          b != expected
        })
        .count() as i32 / 2
    };

    if ones > zeros {
      // Must start with '1'
      count_mismatches(b'1')
    } else if zeros > ones {
      // Must start with '0'
      count_mismatches(b'0')
    } else {
      // Either pattern works, take minimum
      count_mismatches(b'0').min(count_mismatches(b'1'))
    }
  }
}