Minimum Number of Swaps to Make the Binary String Alternating

Medium
1226.

Minimum Number of Swaps to Make the Binary String Alternating

Minimum Number of Swaps to Make the Binary String Alternating is a medium coding problem on strings, greedy and counting, asked in Amazon and Microsoft interviews.

You are given a binary string s. In one swap you may exchange any two characters of s — they do not have to be next to each other.

A string is alternating when no two adjacent characters are equal, like "0101" or "10101".

Return the minimum number of swaps that make s alternating, or -1 if it cannot be done.

Example 1

Input
s = "110100"
Output
1
Explanation
Swap the first and the last character to get `"010101"`.

Example 2

Input
s = "010"
Output
0
Explanation
Already alternating.

Example 3

Input
s = "1110"
Output
-1
Explanation
Three `1`s and one `0` can never alternate.

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Swaps to Make the Binary String Alternating Solution

Minimum Number of Swaps to Make the Binary String Alternating solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Swaps to Make the Binary String Alternating is a medium coding problem on strings, greedy and counting, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Counting
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a binary string s. In one swap you may exchange any two characters of s — they do not have to be next to each other.

A string is alternating when no two adjacent characters are equal, like "0101" or "10101".

Return the minimum number of swaps that make s alternating, or -1 if it cannot be done.

Example 1

Input: s = "110100"
Output: 1
Explanation: Swap the first and the last character to get `"010101"`.

Example 2

Input: s = "010"
Output: 0
Explanation: Already alternating.

Example 3

Input: s = "1110"
Output: -1
Explanation: Three `1`s and one `0` can never alternate.

Constraints

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

Hints for Minimum Number of Swaps to Make the Binary String Alternating

  1. Hint 1

    Swaps never change how many 0s and 1s there are. When is an alternating arrangement possible at all?

  2. Hint 2

    There are only two alternating strings of a given length: one starting with 0, one starting with 1. Which of them have the right counts?

  3. Hint 3

    Against a feasible target, count the mismatched positions. Each swap can fix two of them — one misplaced 0 and one misplaced 1.

How to solve Minimum Number of Swaps to Make the Binary String Alternating

The counts decide which of the two alternating targets are reachable; against a reachable target, the answer is half the number of mismatched positions.

Approach

  1. Count the 1s and 0s. If they differ by more than one, return -1.
  2. For each start bit f in {0, 1}: the target f, 1-f, f, ... needs ceil(n / 2) copies of f. Skip it if s does not have exactly that many.
  3. Count positions i where s[i] differs from the target bit (i + f) % 2; the cost is half that count.
  4. Return the smaller cost among the feasible targets.

Why it works

When the counts match the target, the mismatches split evenly: every position holding a 1 where a 0 belongs is balanced by one holding a 0 where a 1 belongs. One swap of such a pair fixes two mismatches, and no swap can fix more than two, so mismatches / 2 swaps are both enough and necessary. When n is even both targets are feasible and we take the cheaper one; when n is odd only the target starting with the majority bit is feasible.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Swaps are between any two positions, not adjacent ones — this is not a bubble-sort distance.
  • For odd n only one target is feasible; computing the other gives a wrong (smaller) answer.
  • The mismatch count against a feasible target is always even; dividing by two is exact.

Reference solution

Python

def minSwaps(s: str) -> int:
    n = len(s)
    ones = s.count("1")
    zeros = n - ones
    if abs(ones - zeros) > 1:
        return -1
    best = -1
    for f in (0, 1):
        have = zeros if f == 0 else ones
        if have != (n + 1) // 2:
            continue
        miss = 0
        for i, ch in enumerate(s):
            if int(ch) != (i + f) % 2:
                miss += 1
        if best == -1 or miss // 2 < best:
            best = miss // 2
    return best

Java

public static int minSwaps(String s) {
    int n = s.length(), ones = 0;
    for (int i = 0; i < n; i++) if (s.charAt(i) == '1') ones++;
    int zeros = n - ones;
    if (Math.abs(ones - zeros) > 1) return -1;
    int best = -1;
    for (int f = 0; f < 2; f++) {
        int have = f == 0 ? zeros : ones;
        if (have != (n + 1) / 2) continue;
        int miss = 0;
        for (int k = 0; k < n; k++) if (s.charAt(k) - '0' != (k + f) % 2) miss++;
        if (best == -1 || miss / 2 < best) best = miss / 2;
    }
    return best;
}

C++

int minSwaps(string s) {
    int n = s.size(), ones = 0;
    for (char ch : s) if (ch == '1') ones++;
    int zeros = n - ones;
    if (abs(ones - zeros) > 1) return -1;
    int best = -1;
    for (int f = 0; f < 2; f++) {
        int have = f == 0 ? zeros : ones;
        if (have != (n + 1) / 2) continue;
        int miss = 0;
        for (int k = 0; k < n; k++) if (s[k] - '0' != (k + f) % 2) miss++;
        if (best == -1 || miss / 2 < best) best = miss / 2;
    }
    return best;
}

JavaScript

var minSwaps = function(s) {
    var n = s.length, ones = 0;
    for (var i = 0; i < n; i++) if (s[i] === "1") ones++;
    var zeros = n - ones;
    if (Math.abs(ones - zeros) > 1) return -1;
    var best = -1;
    for (var f = 0; f < 2; f++) {
        var have = f === 0 ? zeros : ones;
        if (have !== Math.floor((n + 1) / 2)) continue;
        var miss = 0;
        for (var k = 0; k < n; k++) if (s.charCodeAt(k) - 48 !== (k + f) % 2) miss++;
        if (best === -1 || miss / 2 < best) best = miss / 2;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms