We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Swaps to Make the Binary String Alternating

Difficulty: Medium

Problem Description

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.

Key Insights

  • An alternating string will have an equal number of '0's and '1's or differ by one.
  • If the absolute difference between the number of '0's and '1's is greater than 1, it is impossible to form an alternating string.
  • The minimum swaps needed can be derived from the mismatched positions of '0's and '1's in the string compared to the desired alternating pattern.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We will count the number of '0's and '1's in the given binary string. If the difference in their counts is greater than one, return -1. Otherwise, we will compute the number of mismatches against two possible alternating patterns: starting with '0' and starting with '1'. The minimum number of swaps required will be half the number of mismatches since each swap fixes two positions.

Code Solutions

def min_swaps(s: str) -> int:
    count0 = s.count('0')
    count1 = s.count('1')

    # Check if it is possible to make the string alternating
    if abs(count0 - count1) > 1:
        return -1

    # Mismatches for both patterns
    mismatch_pattern1 = mismatch_pattern2 = 0

    for i in range(len(s)):
        expected_char_pattern1 = '0' if i % 2 == 0 else '1'
        expected_char_pattern2 = '1' if i % 2 == 0 else '0'

        if s[i] != expected_char_pattern1:
            mismatch_pattern1 += 1
        if s[i] != expected_char_pattern2:
            mismatch_pattern2 += 1

    # Minimum swaps needed
    return min(mismatch_pattern1, mismatch_pattern2) // 2
← Back to All Questions