Scale Engineer

Minimum Swaps to Make Strings Equal

Med
#1164Time: O(N), for a single pass over the strings.Space: O(1), as we only use a few integer variables to store the counts, regardless of the input size.1 company
Patterns
MathGreedy
Data structures
String
Companies
J.P. Morgan

Prompt

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.

 

Example 1:

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2:

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you cannot swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

Example 3:

Input: s1 = "xx", s2 = "xy"
Output: -1

 

Constraints:

  • 1 <= s1.length, s2.length <= 1000
  • s1.length == s2.length
  • s1, s2 only contain 'x' or 'y'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach refines the greedy logic by realizing that we don't need to store the actual indices of the mismatches, only their counts. By performing a single pass through the strings, we can count the two types of mismatches and then use a mathematical formula to calculate the minimum swaps directly.

Algorithm

  • Initialize xy_count = 0 and yx_count = 0.
  • Iterate through the strings from i = 0 to N-1:
    • If s1[i] == 'x' and s2[i] == 'y', increment xy_count.
    • If s1[i] == 'y' and s2[i] == 'x', increment yx_count.
  • If (xy_count + yx_count) % 2 != 0, return -1.
  • Calculate and return the result using the formula: (xy_count / 2) + (yx_count / 2) + (xy_count % 2) * 2.

Walkthrough

This is the most efficient solution. It's based on the same logic as the previous approach but optimizes space by avoiding the lists.

The core insights are:

  • Any two mismatches of the same type (e.g., two s1[i]='x', s2[i]='y' pairs) can be resolved in one swap.
  • Any two mismatches of different types (one xy and one yx) can be resolved in two swaps.

We iterate through the strings once, maintaining two counters: xy_count for s1[i]='x', s2[i]='y' mismatches, and yx_count for s1[i]='y', s2[i]='x' mismatches.

First, we check the impossibility condition: the total number of mismatches, xy_count + yx_count, must be even. If not, we return -1. An even total implies that xy_count and yx_count have the same parity (both even or both odd).

The total swaps can then be calculated:

  • xy_count / 2 swaps for the pairs of 'xy' mismatches.
  • yx_count / 2 swaps for the pairs of 'yx' mismatches.
  • If xy_count is odd (meaning yx_count is also odd), we have one leftover 'xy' and one leftover 'yx' mismatch. These two require 2 swaps to resolve. This adds (xy_count % 2) * 2 to the total.

A more concise mathematical formula that captures this logic is (xy_count + 1) / 2 + (yx_count + 1) / 2.

class Solution {    public int minimumSwap(String s1, String s2) {        int xy_count = 0;        int yx_count = 0;         for (int i = 0; i < s1.length(); i++) {            char c1 = s1.charAt(i);            char c2 = s2.charAt(i);            if (c1 == 'x' && c2 == 'y') {                xy_count++;            } else if (c1 == 'y' && c2 == 'x') {                yx_count++;            }        }         if ((xy_count + yx_count) % 2 != 0) {            return -1;        }         int result = xy_count / 2;        result += yx_count / 2;        if (xy_count % 2 == 1) {            // A remaining 'xy' and 'yx' mismatch requires 2 swaps.            result += 2;        }                return result;    }}

Complexity

Time

O(N), for a single pass over the strings.

Space

O(1), as we only use a few integer variables to store the counts, regardless of the input size.

Trade-offs

Pros

  • Optimal solution with O(N) time and O(1) space complexity.

  • Simple and elegant implementation once the logic is understood.

Cons

  • The mathematical formula might seem non-obvious without a careful analysis of the swap operations.

Solutions

class Solution { public int minimumSwap ( String s1 , String s2 ) { int xy = 0 , yx = 0 ; for ( int i = 0 ; i < s1 . length (); ++ i ) { char a = s1 . charAt ( i ), b = s2 . charAt ( i ); if ( a < b ) { ++ xy ; } if ( a > b ) { ++ yx ; } } if (( xy + yx ) % 2 == 1 ) { return - 1 ; } return xy / 2 + yx / 2 + xy % 2 + yx % 2 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem