LeetCode 1864 - Minimum Number of Swaps to Make the Binary String Alternating

The problem gives us a binary string s that contains only '0' and '1'. We are allowed to swap any two characters in the string, not necessarily adjacent ones. Our goal is to transform the string into an alternating binary string using the minimum number of swaps.

leetcodemediumstringgreedy

LeetCode Problem 1864

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

LeetCode 1864 - Minimum Number of Swaps to Make the Binary String Alternating

Problem Understanding

The problem gives us a binary string s that contains only '0' and '1'. We are allowed to swap any two characters in the string, not necessarily adjacent ones. Our goal is to transform the string into an alternating binary string using the minimum number of swaps.

An alternating binary string is one where no two neighboring characters are the same. This means the string must follow one of two possible patterns:

  • "010101..."
  • "101010..."

For example:

  • "010" is alternating
  • "1010" is alternating
  • "110" is not alternating because the first two characters are equal

The output should be the minimum number of swaps required to make the string alternating. If it is impossible, we must return -1.

The constraint 1 <= s.length <= 1000 tells us the input size is relatively small, but we should still aim for an efficient linear-time solution. Since the string contains only two characters, the structure of valid alternating strings is extremely constrained, which suggests that we can reason about counts and positions instead of trying every possible swap arrangement.

A very important observation is that an alternating string can only exist if the counts of '0' and '1' differ by at most 1.

For example:

  • "0101" has two 0s and two 1s, valid
  • "101" has one 0 and two 1s, valid
  • "1110" has one 0 and three 1s, impossible

Some edge cases that can easily cause bugs include:

  • Strings that are already alternating
  • Strings where one character appears much more often than the other
  • Strings of length 1
  • Strings with equal counts, where both alternating patterns are possible
  • Strings with unequal counts, where only one starting pattern is valid

Understanding these cases upfront helps avoid incorrect assumptions during implementation.

Approaches

Brute Force Approach

A brute-force solution would try all possible swaps and search for the minimum number of operations needed to produce an alternating string.

One way to think about this is as a graph problem. Each string state is a node, and each swap creates another node. We could use breadth-first search to find the shortest path to an alternating string.

This approach is correct because BFS guarantees the minimum number of swaps. However, it is computationally infeasible because the number of possible string states grows factorially with the length of the string. Even for moderate input sizes, the search space becomes enormous.

Another brute-force variation would generate both target alternating patterns and simulate swaps directly by trying different mismatched positions. While better than BFS, it still does unnecessary work compared to the optimal greedy observation.

Optimal Greedy Approach

The key insight is that an alternating binary string has a completely fixed structure.

For a string of length n, there are at most two valid target patterns:

  • Start with 0: "010101..."
  • Start with 1: "101010..."

Instead of searching through swaps, we can compare the current string against these target patterns.

Whenever a character does not match the expected character at a position, that position is "wrong". Every swap fixes two wrong positions simultaneously, because swapping a misplaced 0 with a misplaced 1 corrects both.

Therefore:

  • Count how many positions mismatch the target pattern
  • The minimum swaps needed is mismatches / 2

We only need to consider valid target patterns based on character counts.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Explores enormous swap state space
Optimal O(n) O(1) Counts mismatches against valid alternating patterns

Algorithm Walkthrough

  1. Count the number of '0' characters and '1' characters in the string.

This step determines whether forming an alternating string is even possible. In a valid alternating string, the counts can differ by at most 1. 2. Check feasibility.

If abs(count0 - count1) > 1, return -1.

No arrangement can alternate properly when one character appears too many times. 3. Define a helper function that computes swaps needed for a target starting character.

For example, if the target starts with '0', the expected pattern becomes:

  • index 0 -> '0'
  • index 1 -> '1'
  • index 2 -> '0'
  • and so on

We compare each position with its expected value and count mismatches. 4. Count mismatched positions.

Every mismatch means the current character is not where it belongs in the target alternating pattern. 5. Divide mismatches by 2.

A single swap fixes two mismatched positions simultaneously. Therefore, the minimum swaps required equals mismatches // 2. 6. Determine which target patterns are valid.

  • If counts are equal, both starting patterns are possible. Return the smaller result.
  • If zeros are more frequent, the string must start with '0'.
  • If ones are more frequent, the string must start with '1'.

Why it works

The algorithm works because every alternating binary string has a uniquely determined character at each index once the starting character is chosen. Any mismatch represents a character that belongs somewhere else. Since swapping two misplaced characters fixes both positions simultaneously, the optimal number of swaps is exactly half the mismatch count. The count feasibility condition guarantees that a valid alternating arrangement exists.

Python Solution

class Solution:
    def minSwaps(self, s: str) -> int:
        zeros = s.count('0')
        ones = len(s) - zeros

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

        def count_swaps(start_char: str) -> int:
            mismatches = 0

            for i, ch in enumerate(s):
                expected = start_char if i % 2 == 0 else (
                    '1' if start_char == '0' else '0'
                )

                if ch != expected:
                    mismatches += 1

            return mismatches // 2

        if zeros > ones:
            return count_swaps('0')

        if ones > zeros:
            return count_swaps('1')

        return min(count_swaps('0'), count_swaps('1'))

The implementation begins by counting zeros and ones. This immediately tells us whether an alternating arrangement is possible.

The helper function count_swaps computes how many swaps are needed if the alternating string starts with a particular character. It iterates through every index and determines the expected character at that position. If the actual character differs, the mismatch counter increases.

At the end of the scan, mismatches are divided by two because each swap resolves two incorrect positions.

The final section determines which alternating pattern is valid based on character frequencies. If both patterns are valid, the minimum result is returned.

Go Solution

func minSwaps(s string) int {
    zeros := 0

    for _, ch := range s {
        if ch == '0' {
            zeros++
        }
    }

    ones := len(s) - zeros

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

    countSwaps := func(start byte) int {
        mismatches := 0

        for i := 0; i < len(s); i++ {
            expected := start

            if i%2 == 1 {
                if start == '0' {
                    expected = '1'
                } else {
                    expected = '0'
                }
            }

            if s[i] != expected {
                mismatches++
            }
        }

        return mismatches / 2
    }

    if zeros > ones {
        return countSwaps('0')
    }

    if ones > zeros {
        return countSwaps('1')
    }

    swapsStartingWithZero := countSwaps('0')
    swapsStartingWithOne := countSwaps('1')

    if swapsStartingWithZero < swapsStartingWithOne {
        return swapsStartingWithZero
    }

    return swapsStartingWithOne
}

func abs(x int) int {
    if x < 0 {
        return -x
    }

    return x
}

The Go implementation follows the same logic as the Python version. One notable difference is that Go uses byte values for character comparison. The helper function is implemented as a closure, which keeps the code concise and avoids unnecessary duplication.

Go does not provide a built-in integer abs function, so we define a small helper manually.

Worked Examples

Example 1

Input:

s = "111000"

Count characters:

Character Count
0 3
1 3

Both alternating patterns are valid.

Target Pattern: "101010"

Index Actual Expected Mismatch
0 1 1 No
1 1 0 Yes
2 1 1 No
3 0 0 No
4 0 1 Yes
5 0 0 No

Total mismatches = 2

Swaps needed = 2 // 2 = 1

Target Pattern: "010101"

Index Actual Expected Mismatch
0 1 0 Yes
1 1 1 No
2 1 0 Yes
3 0 1 Yes
4 0 0 No
5 0 1 Yes

Total mismatches = 4

Swaps needed = 4 // 2 = 2

Minimum result = 1

Example 2

Input:

s = "010"

Counts:

Character Count
0 2
1 1

Since zeros are more frequent, the string must start with 0.

Expected pattern:

010
Index Actual Expected Mismatch
0 0 0 No
1 1 1 No
2 0 0 No

Mismatches = 0

Swaps needed = 0

Example 3

Input:

s = "1110"

Counts:

Character Count
0 1
1 3

Difference = 2

Since the difference exceeds 1, no alternating arrangement exists.

Return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the string a constant number of times
Space O(1) Only a few counters and variables are used

The algorithm performs linear scans over the input string. Each character is processed a constant number of times, resulting in linear time complexity. No auxiliary data structures proportional to input size are allocated, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.minSwaps("111000") == 1  # Example case with one optimal swap
assert sol.minSwaps("010") == 0  # Already alternating
assert sol.minSwaps("1110") == -1  # Impossible due to count imbalance

assert sol.minSwaps("0") == 0  # Single character
assert sol.minSwaps("1") == 0  # Single character

assert sol.minSwaps("01") == 0  # Already alternating
assert sol.minSwaps("10") == 0  # Already alternating

assert sol.minSwaps("00") == -1  # Impossible, all same
assert sol.minSwaps("11") == -1  # Impossible, all same

assert sol.minSwaps("1001") == 1  # One swap needed
assert sol.minSwaps("0110") == 1  # One swap needed

assert sol.minSwaps("101010") == 0  # Longer alternating string
assert sol.minSwaps("010101") == 0  # Longer alternating string

assert sol.minSwaps("1100") == 1  # Equal counts, choose best pattern
assert sol.minSwaps("0011") == 1  # Equal counts, choose best pattern

assert sol.minSwaps("101100") == 1  # Mixed ordering
assert sol.minSwaps("000111") == 1  # Clustered characters
Test Why
"111000" Standard case requiring one swap
"010" Already alternating
"1110" Impossible due to frequency imbalance
"0" Minimum length input
"1" Minimum length input
"01" Small valid alternating string
"10" Small valid alternating string
"00" Impossible with identical characters
"11" Impossible with identical characters
"1001" Requires a single corrective swap
"0110" Symmetric mismatch case
"101010" Larger already-valid pattern
"010101" Alternate valid pattern
"1100" Equal counts with two possible targets
"0011" Another balanced configuration
"101100" Random mixed arrangement
"000111" Grouped characters requiring swap

Edge Cases

One important edge case is when the string length is 1. A single character is always alternating because there are no adjacent characters to violate the condition. Naive implementations sometimes incorrectly attempt swaps or reject unequal counts without considering this trivial case. The current implementation handles this naturally because the mismatch count becomes zero.

Another critical edge case occurs when the counts of zeros and ones differ by more than one. For example, "1110" contains three ones and one zero. No matter how characters are rearranged, at least two ones must end up adjacent. The implementation explicitly checks this condition before attempting any further processing and immediately returns -1.

A third subtle edge case appears when counts are equal. In these situations, both alternating patterns are theoretically possible. For example, "111000" can target either "101010" or "010101". A buggy implementation might only check one pattern and miss the optimal answer. This solution evaluates both possibilities and returns the minimum swap count.