Minimum Number of Swaps to Make the Binary String Alternating

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible. An alternating string has no two adjacent characters that are equal. A swap picks any two positions in the string and exchanges their characters.

This is LeetCode 1864: Minimum Number of Swaps to Make the Binary String Alternating, a medium-difficulty problem that tests your ability to think about string structure through counting rather than simulation.

Why this problem matters

Binary string problems show up frequently in interviews, and this one combines two common patterns: counting character frequencies and reasoning about target configurations. Many candidates try to simulate swaps or use dynamic programming, but the real trick is realizing you can solve it with pure counting in O(n) time.

The greedy insight here transfers to any problem where you need to rearrange characters into a known target pattern. Instead of searching for the best sequence of moves, you figure out how many positions are wrong and use that count directly.

The approach

There are only two possible alternating strings of length n: one that starts with '0' (like "010101...") and one that starts with '1' (like "101010..."). The key observations are:

1. Feasibility check. For an alternating string to exist, the counts of '0' and '1' must differ by at most 1. If the difference is 2 or more, return -1.

2. Which patterns are valid? If there are more '1's than '0's, the string must start with '1'. If there are more '0's, it must start with '0'. If the counts are equal, both starting characters work.

3. Counting mismatches. For each valid target pattern, count how many positions in s have the wrong character. Every swap fixes exactly two wrong positions (one has a '0' where it needs a '1', and the other has a '1' where it needs a '0'). So the number of swaps equals mismatches divided by 2.

4. Take the minimum over all valid target patterns.

The solution

def minSwaps(s):
    ones = s.count('1')
    zeros = len(s) - ones

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

    def count_mismatches(start_char):
        mismatches = 0
        for i, ch in enumerate(s):
            expected = str((start_char + i) % 2)
            if ch != expected:
                mismatches += 1
        return mismatches // 2

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

Here is what each piece does:

1. Count ones and zeros. A single pass gives you both counts.
2. Check feasibility. If the counts differ by more than 1, no alternating arrangement exists.
3. Count mismatches for a target pattern. The start_char parameter determines whether the pattern begins with '0' or '1'. At each index, compute the expected character and compare it to the actual character.
4. Divide mismatches by 2. Each swap fixes two mismatches, so the number of swaps is exactly half the mismatch count.
5. Return the minimum across valid patterns.

Step-by-step walkthrough

The walkthrough above uses s = "11100". With 3 ones and 2 zeros, only the pattern starting with '1' is valid. Two positions mismatch (indices 1 and 4), and one swap fixes both. The answer is 1.

Complexity analysis

You make at most two passes through the string: one to count characters, and one (or two) to count mismatches against target patterns. No extra data structures are needed beyond a few integer variables.

The building blocks

Character frequency counting

Counting how many times each character appears is the foundation of this solution. You see this pattern everywhere:

ones = s.count('1')
zeros = len(s) - ones

The same technique applies to anagram detection, frequency-based grouping, and any problem where the arrangement does not matter, only the counts.

Mismatch counting against a known target

When you know exactly what the target string should look like, you do not need to build it. Just iterate through the input and count positions where the actual character differs from the expected one:

for i, ch in enumerate(s):
    expected = str((start_char + i) % 2)
    if ch != expected:
        mismatches += 1

This pattern appears in problems involving rotations, cyclic patterns, and any scenario where the target is deterministic given some parameter.

Edge cases

Before submitting, make sure your solution handles these:

• Already alternating "0101": zero mismatches for the '0'-start pattern. Answer is 0.
• Single character "1" or "0": already alternating by definition. Answer is 0.
• Impossible "111": three 1s, zero 0s. Difference is 3, which exceeds 1. Answer is -1.
• Equal counts "1100": both patterns are valid. Pattern "1010" has 2 mismatches (1 swap). Pattern "0101" has 2 mismatches (1 swap). Answer is 1.
• All same character "0000": four 0s, zero 1s. Difference is 4. Answer is -1.
• Odd length, equal difference of 1 "11010": three 1s, two 0s. Only "10101" is valid. Count mismatches and divide by 2.

From understanding to recall

You have read the counting-based solution and it makes sense. Count characters, check feasibility, compare against target patterns, divide mismatches by 2. But can you reproduce it from scratch under interview pressure?

The details that trip people up: remembering to check abs(ones - zeros) > 1 before doing anything else, correctly generating the expected character with (start_char + i) % 2, knowing that only certain patterns are valid when counts are unequal, and dividing by 2 at the end rather than trying to simulate individual swaps.

Spaced repetition locks these details in. You practice writing the solution from memory at increasing intervals until the pattern is automatic. When you see "make a binary string alternating" in your interview, the counting approach flows out without hesitation.

Related posts

• Is Subsequence - String pattern matching using two-pointer traversal
• Minimum Deletions to Make Character Frequencies Unique - Greedy frequency manipulation on strings
• Check if Binary String Has at Most One Segment of Ones - Binary string structure analysis

CodeBricks breaks this problem into its frequency counting and mismatch counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy string rearrangement question shows up in your interview, you do not think about it. You just write it.

The greedy mismatch counting pattern is one of the reusable building blocks that covers dozens of LeetCode problems involving string rearrangement. Learning it once and drilling it with spaced repetition is far more effective than grinding random problems and hoping they stick.