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 Swaps to Make Strings Equal

Number: 1369

Difficulty: Medium

Paid? No

Companies: Google, J.P. Morgan

Problem Description

Given two strings s1 and s2 of equal length that consist only of the characters "x" and "y", the goal is to make the strings identical by swapping characters between the two strings (i.e., you can only swap s1[i] with s2[j]). Return the minimum number of swaps needed or -1 if it is impossible.

Key Insights

  • Identify positions where characters differ between s1 and s2.
  • Count mismatches of type "xy" (s1 has 'x', s2 has 'y') and type "yx" (s1 has 'y', s2 has 'x').
  • Two mismatches of the same type (either "xy" or "yx") can be fixed in one swap.
  • If there is one unmatched "xy" and one unmatched "yx", they require 2 swaps.
  • If the total number of mismatches is odd, it is impossible to make the strings equal.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings. Space Complexity: O(1), only a few integer counters are used.

Solution

The approach is to traverse the strings once while counting the mismatches:

  1. Count the number of "xy" mismatches and the number of "yx" mismatches.
  2. If the sum of these mismatches is odd, return -1 because it's impossible to fix the imbalance.
  3. Every pair of "xy" or "yx" mismatches can be fixed with one swap, contributing xy // 2 + yx // 2 swaps.
  4. If there is an odd mismatch in both "xy" and "yx" counts (one leftover from each), these can be fixed by 2 additional swaps.
  5. Sum these values to get the total minimum number of swaps required.

Data structures used include simple counters (integers), and the algorithm uses a greedy approach to pair up mismatches optimally.

Code Solutions

# Function to calculate the minimum swaps to make the two strings equal.
def minimumSwap(s1: str, s2: str) -> int:
    # counters for mismatches
    xy, yx = 0, 0
    
    # iterate over the string characters.
    for c1, c2 in zip(s1, s2):
        # if character in s1 is 'x' and in s2 is 'y', it's an "xy" mismatch.
        if c1 == 'x' and c2 == 'y':
            xy += 1
        # if character in s1 is 'y' and in s2 is 'x', it's a "yx" mismatch.
        elif c1 == 'y' and c2 == 'x':
            yx += 1
    
    # if the total mismatches are odd, it's impossible to balance them.
    if (xy + yx) % 2 != 0:
        return -1
    
    # swaps for pairs of identical mismatches
    swaps = (xy // 2) + (yx // 2)
    
    # if there is an extra "xy" and an extra "yx", they take 2 additional swaps.
    if xy % 2 == 1 and yx % 2 == 1:
        swaps += 2
        
    return swaps

# Example test cases
print(minimumSwap("xx", "yy"))  # Output: 1
print(minimumSwap("xy", "yx"))  # Output: 2
print(minimumSwap("xx", "xy"))  # Output: -1
← Back to All Questions