Minimum Swaps to Make Strings Equal - Practice Coding Problems

Minimum Swaps to Make Strings Equal - Problem

You are given two strings s1 and s2 of equal length consisting of letters 'x' and 'y' only.

Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

Input & Output

Example 1 — Equal xy mismatches

$ Input: s1 = "xx", s2 = "yy"

› Output: 1

💡 Note: Two xy mismatches at positions 0 and 1. Swap s1[0] with s2[1]: s1="yx", s2="yx". One swap makes them equal.

Example 2 — Mixed mismatch types

$ Input: s1 = "xy", s2 = "yx"

› Output: 2

💡 Note: One xy mismatch at pos 0, one yx mismatch at pos 1. Need 2 swaps: swap s1[0] with s1[1] via s2[0], then fix remaining.

Example 3 — Impossible case

$ Input: s1 = "xx", s2 = "xy"

› Output: -1

💡 Note: Only 1 mismatch (odd number). Cannot make strings equal since total x's and y's must be even.

Constraints

1 ≤ s1.length, s2.length ≤ 1000
s1.length == s2.length
s1[i] and s2[i] are either 'x' or 'y'

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Two strings with only 'x' and 'y' characters

Count Patterns

Count xy and yx mismatches

Apply Formula

Calculate minimum swaps using mathematical pattern

Key Takeaway

🎯 Key Insight: Two mismatches of the same type need only 1 swap, mixed types need 2 swaps each

Asked in

G Google 15 f Facebook 12 a Amazon 8

The optimal approach counts mismatch patterns: xy (s1='x', s2='y') and yx (s1='y', s2='x'). If total mismatches is odd, return -1. Otherwise, use formula: (xy + 1) / 2 + (yx + 1) / 2. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Swaps	O(2^n)	O(n)	Try all possible swaps recursively until strings match
Count Mismatches - Optimal	O(n)	O(1)	Count xy and yx patterns to calculate minimum swaps mathematically

Brute Force - Try All Swaps — Algorithm Steps

Find all mismatch positions
Try swapping each pair recursively
Return minimum swaps needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Mismatch

Identify positions where s1[i] ≠ s2[i]

Try Swaps

Recursively try all swap combinations

Return Min

Return minimum swaps found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int backtrack(char* s1, char* s2, int swaps, int n) {
    if (strcmp(s1, s2) == 0) {
        return swaps;
    }
    
    int minSwaps = INT_MAX;
    
    // Find first mismatch
    int mismatchIdx = -1;
    for (int i = 0; i < n; i++) {
        if (s1[i] != s2[i]) {
            mismatchIdx = i;
            break;
        }
    }
    
    if (mismatchIdx == -1) return swaps;
    
    // Try swapping with all other positions
    for (int j = mismatchIdx + 1; j < n; j++) {
        if (s1[mismatchIdx] != s2[mismatchIdx] || s1[j] != s2[j]) {
            // Try swap s1[mismatchIdx] with s2[j]
            char temp = s1[mismatchIdx];
            s1[mismatchIdx] = s2[j];
            s2[j] = temp;
            int result1 = backtrack(s1, s2, swaps + 1, n);
            if (result1 < minSwaps) minSwaps = result1;
            temp = s1[mismatchIdx];
            s1[mismatchIdx] = s2[j];
            s2[j] = temp;
            
            // Try swap s2[mismatchIdx] with s1[j]
            temp = s2[mismatchIdx];
            s2[mismatchIdx] = s1[j];
            s1[j] = temp;
            int result2 = backtrack(s1, s2, swaps + 1, n);
            if (result2 < minSwaps) minSwaps = result2;
            temp = s2[mismatchIdx];
            s2[mismatchIdx] = s1[j];
            s1[j] = temp;
        }
    }
    
    return minSwaps;
}

int solution(char* s1, char* s2) {
    int n = strlen(s1);
    char* s1Copy = malloc((n + 1) * sizeof(char));
    char* s2Copy = malloc((n + 1) * sizeof(char));
    strcpy(s1Copy, s1);
    strcpy(s2Copy, s2);
    
    int result = backtrack(s1Copy, s2Copy, 0, n);
    free(s1Copy);
    free(s2Copy);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char s1[1001], s2[1001];
    fgets(s1, sizeof(s1), stdin);
    s1[strcspn(s1, "\n")] = 0;
    fgets(s2, sizeof(s2), stdin);
    s2[strcspn(s2, "\n")] = 0;
    
    int result = solution(s1, s2);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Recursive branching tries all possible swap combinations exponentially

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth can go up to n levels

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Swaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler