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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Swaps to Make the Binary String Alternating

Number: 1994

Difficulty: Medium

Paid? No

Companies: Societe Generale

Problem Description

Given a binary string s, the goal is to return the minimum number of character swaps needed to make s alternating (i.e. no two adjacent characters are equal). A swap can be performed between any two positions. If it is impossible to form an alternating string, return -1.

Key Insights

  • Only two alternating patterns are possible: one starting with '0' (e.g., "0101...") and one starting with '1' (e.g., "1010...").
  • A valid alternating string imposes a constraint on the counts of '0's and '1's. For a string of even length, the counts must be equal; for an odd length, the difference must be exactly one.
  • When comparing the given string to a candidate alternating pattern, each position that does not match represents a "misplaced" character.
  • Since swapping any two misplaced characters will correct two positions at once, the number of swaps required is half the number of mismatches.
  • For odd-length strings the valid candidate pattern is determined by the majority character.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because we iterate over the string a constant number of times. Space Complexity: O(1), since only a few integer variables are used regardless of the input size.

Solution

The solution involves the following steps:

  1. Count the number of '0's and '1's in the string.
  2. Based on these counts, check if forming an alternating string is possible:
    • For even-length strings, the counts must be equal.
    • For odd-length strings, the difference between counts must be exactly one.
  3. Construct the two candidate alternating strings:
    • One starting with '0' (i.e., "0101...")
    • One starting with '1' (i.e., "1010...")
  4. For each candidate pattern, iterate through s and count the mismatches.
  5. Since each swap fixes two mismatches, the number of swaps is determined by dividing the mismatch count by 2.
  6. For even-length strings, return the minimum swaps from the two candidates.
  7. For odd-length strings, only the candidate that aligns with the majority element is valid.

Key data structures: simple integer counters and iterative loops. The trick is to realize a swap handles two mismatches simultaneously, so we can count only the positions that are off and then divide by two for the final answer.

Code Solutions

# Python solution with line-by-line comments

def minSwaps(s: str) -> int:
    n = len(s)
    # Count the occurrences of '0' and '1'
    count0 = s.count('0')
    count1 = s.count('1')
    
    # Check feasibility based on counts
    # For even-length strings, counts must be equal.
    # For odd-length strings, the difference between counts must be exactly 1.
    if n % 2 == 0:
        if count0 != count1:
            return -1
    else:
        if abs(count0 - count1) != 1:
            return -1

    # Helper function to compute mismatches with candidate pattern
    def mismatches(start_char: str) -> int:
        mismatch = 0
        expected = start_char
        for char in s:
            # Compare current character with expected character in alternating pattern
            if char != expected:
                mismatch += 1
            # Flip expected character ('0' becomes '1' and vice versa)
            expected = '1' if expected == '0' else '0'
        return mismatch

    # For even-length strings, both patterns are possible
    if n % 2 == 0:
        swaps_start0 = mismatches('0')
        swaps_start1 = mismatches('1')
        # Each swap fixes two mismatches
        return min(swaps_start0, swaps_start1) // 2
    else:
        # For odd-length strings, determine which pattern is valid based on the majority element
        if count0 > count1:
            # The valid pattern must start with '0'
            return mismatches('0') // 2
        else:
            # The valid pattern must start with '1'
            return mismatches('1') // 2

# Example usage:
# print(minSwaps("111000"))  # Output: 1
← Back to All Questions