Problem Description

You are given a binary string s that contains only characters '0' and '1'. Your task is to find the minimum number of character swaps needed to make the string alternating, or return -1 if it's impossible.

An alternating string is one where no two adjacent characters are the same. For example:

• "010" and "1010" are alternating strings (characters alternate between 0 and 1)
• "0100" is not alternating (has two consecutive 0s)

When performing a swap, you can exchange any two characters in the string, even if they are not adjacent to each other.

The key insight is that an alternating string can only have two patterns:

1. Starting with '0': "0101010..."
2. Starting with '1': "1010101..."

For a string to be convertible to an alternating pattern:

• If the string has even length, it must have equal numbers of 0s and 1s
• If the string has odd length, one character must appear exactly one more time than the other

The solution counts how many positions need to be corrected to match each possible alternating pattern, then determines the minimum swaps needed (each swap fixes two positions, so the number of swaps is half the number of mismatched positions).

Intuition

To understand how to solve this problem, let's think about what an alternating string looks like and what constraints we have.

First, we need to recognize that there are only two possible alternating patterns for any string:

• Pattern A: "0101010..." (starting with 0)
• Pattern B: "1010101..." (starting with 1)

For a string to be transformable into an alternating pattern, we need the right count of 0s and 1s. If the string has length n:

• For even n: we need exactly n/2 zeros and n/2 ones
• For odd n: we need either (n+1)/2 zeros and (n-1)/2 ones, or vice versa

If the counts don't match these requirements, it's impossible to create an alternating string no matter how many swaps we make, so we return -1.

Now, how do we count the minimum swaps needed? The key insight is that when we swap two characters, we're fixing two positions at once. For example, if position 2 needs a '0' but has a '1', and position 5 needs a '1' but has a '0', one swap fixes both positions.

To calculate the swaps for a target pattern:

1. Count how many positions have the wrong character compared to the target pattern
2. Since each swap fixes exactly 2 positions, the number of swaps needed is half of the mismatched positions

When we have equal counts of 0s and 1s, we could form either pattern (starting with 0 or starting with 1), so we calculate swaps for both and take the minimum. When counts are unequal, only one pattern is possible - the one that starts with the more frequent character.

The function calc(c) implements this by checking each position: if position i should have character (c + i) % 2 but doesn't, we count it as a mismatch. The total mismatches divided by 2 gives us the swap count.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a systematic approach to determine the minimum swaps needed:

Step 1: Count the characters

First, we count the occurrences of '0' and '1' in the string:

n0 = s.count("0")
n1 = len(s) - n0

Step 2: Check feasibility

We check if it's possible to create an alternating string by examining the difference between counts:

if abs(n0 - n1) > 1:
    return -1

If the absolute difference is greater than 1, it's impossible to form an alternating string.

Step 3: Define the calculation function

The core logic is in the calc(c) function, which calculates the number of swaps needed to form an alternating string starting with character c:

def calc(c: int) -> int:
    return sum((c ^ i & 1) != x for i, x in enumerate(map(int, s))) // 2

This function works by:

• Iterating through each position i and character x in the string
• Using (c ^ i & 1) to determine what character should be at position i:
  • If c = 0 and i is even, or c = 1 and i is odd: expects '0'
  • If c = 0 and i is odd, or c = 1 and i is even: expects '1'
• Counting mismatches where the actual character x doesn't match the expected character
• Dividing by 2 since each swap fixes two mismatched positions

Step 4: Determine which pattern(s) to check

Based on the character counts:

• Equal counts (n0 == n1): Both patterns are possible

  if n0 == n1:
      return min(calc(0), calc(1))

  We calculate swaps for both patterns (starting with 0 and starting with 1) and return the minimum.

• Unequal counts: Only one pattern is possible

  return calc(0 if n0 > n1 else 1)

  We must start with the more frequent character. If there are more 0s, the pattern must be "010101...", otherwise it must be "101010...".

The algorithm has a time complexity of O(n) where n is the length of the string, as we traverse the string a constant number of times. The space complexity is O(1) as we only use a few variables to store counts and results.

Example Walkthrough

Let's walk through the solution with the string s = "111000".

Step 1: Count characters

• Count of '0's: n0 = 3
• Count of '1's: n1 = 3
• String length: n = 6

Step 2: Check feasibility

• abs(3 - 3) = 0, which is ≤ 1, so it's possible to form an alternating string

Step 3: Determine possible patterns Since n0 == n1, we can form either pattern:

• Pattern A: "010101" (starting with 0)
• Pattern B: "101010" (starting with 1)

Step 4: Calculate swaps for Pattern A ("010101")

Let's trace through calc(0):

• Position 0: Should be '0', actual is '1' → mismatch ✗
• Position 1: Should be '1', actual is '1' → match ✓
• Position 2: Should be '0', actual is '1' → mismatch ✗
• Position 3: Should be '1', actual is '0' → mismatch ✗
• Position 4: Should be '0', actual is '0' → match ✓
• Position 5: Should be '1', actual is '0' → mismatch ✗

Total mismatches = 4 Swaps needed = 4 ÷ 2 = 2

We can verify: swap positions (0,3) and (2,5):

• "111000" → "011100" (after swapping positions 0 and 3)
• "011100" → "010101" (after swapping positions 2 and 5)

Step 5: Calculate swaps for Pattern B ("101010")

Let's trace through calc(1):

• Position 0: Should be '1', actual is '1' → match ✓
• Position 1: Should be '0', actual is '1' → mismatch ✗
• Position 2: Should be '1', actual is '1' → match ✓
• Position 3: Should be '0', actual is '0' → match ✓
• Position 4: Should be '1', actual is '0' → mismatch ✗
• Position 5: Should be '0', actual is '0' → match ✓

Total mismatches = 2 Swaps needed = 2 ÷ 2 = 1

We can verify: swap positions (1,4):

• "111000" → "101010" (after swapping positions 1 and 4)

Step 6: Return minimum min(2, 1) = 1

The minimum number of swaps needed is 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm performs the following operations:

• s.count("0") iterates through the string once: O(n)
• len(s) - n0 is a constant time operation: O(1)
• The calc function iterates through the string once using enumerate(map(int, s)) and performs constant-time operations for each character: O(n)
• In the worst case (when n0 == n1), the calc function is called twice, but this is still 2 * O(n) = O(n)

Therefore, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables n0 and n1 store integer counts: O(1)
• The calc function creates an iterator with map(int, s) which doesn't create a new list but processes elements on-the-fly: O(1)
• The sum operation accumulates a single integer value: O(1)
• No additional data structures that scale with input size are created

Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Calculating the Number of Swaps

A frequent mistake is thinking that the number of swaps equals the total number of mismatched positions. This leads to returning mismatches instead of mismatches // 2.

Why this happens: When comparing the current string to the target alternating pattern, we count each position that doesn't match. However, a single swap operation fixes TWO mismatched positions simultaneously - one character moves to where it should be, and another character takes its place.

Incorrect approach:

def calculate_swaps_for_pattern(starting_digit: int) -> int:
    mismatches = 0
    for position, current_char in enumerate(s):
        expected_digit = (starting_digit ^ position) & 1
        if expected_digit != int(current_char):
            mismatches += 1
    return mismatches  # WRONG: Returns total mismatches, not swaps

Correct approach:

def calculate_swaps_for_pattern(starting_digit: int) -> int:
    mismatches = 0
    for position, current_char in enumerate(s):
        expected_digit = (starting_digit ^ position) & 1
        if expected_digit != int(current_char):
            mismatches += 1
    return mismatches // 2  # CORRECT: Each swap fixes 2 positions

2. Misunderstanding Which Pattern to Check When Counts Are Unequal

When the counts of '0' and '1' differ by 1, only one alternating pattern is valid. A common error is checking the wrong pattern or always defaulting to one pattern.

Incorrect approach:

if count_zeros != count_ones:
    return calculate_swaps_for_pattern(0)  # WRONG: Always starts with 0

Correct approach:

if count_zeros > count_ones:
    return calculate_swaps_for_pattern(0)  # More 0s, must start with 0
else:
    return calculate_swaps_for_pattern(1)  # More 1s, must start with 1

3. Confusion with the XOR Logic for Pattern Generation

The expression (starting_digit ^ position) & 1 can be confusing. Developers might incorrectly implement the alternating pattern check.

Common mistakes:

• Using starting_digit + position instead of XOR
• Forgetting the & 1 to get the least significant bit
• Inverting the logic

Understanding the XOR pattern:

• When starting_digit = 0: positions 0,2,4... should have '0', positions 1,3,5... should have '1'
• When starting_digit = 1: positions 0,2,4... should have '1', positions 1,3,5... should have '0'

Alternative clearer implementation:

def calculate_swaps_for_pattern(starting_digit: int) -> int:
    mismatches = 0
    for position, current_char in enumerate(s):
        # More explicit pattern determination
        if position % 2 == 0:
            expected_digit = starting_digit
        else:
            expected_digit = 1 - starting_digit
      
        if expected_digit != int(current_char):
            mismatches += 1
  
    return mismatches // 2

4. Not Handling Edge Cases Properly

Missing validation for impossible cases:

# Forgetting this check will cause incorrect results
if abs(count_zeros - count_ones) > 1:
    return -1

Without this check, the algorithm might return a swap count for strings that cannot be made alternating, such as "0000" or "111".