Minimum Swaps to Make Strings Equal

Minimum Swaps to Make Strings Equal

What is this problem about?

The Minimum Swaps to Make Strings Equal problem gives you two strings of equal length containing only 'x' and 'y'. You can swap any character from the first string with any character from the second string. The goal is to find the minimum number of such swaps to make both strings equal. This Minimum Swaps to Make Strings Equal interview question is a greedy math problem that rewards careful case analysis.

Why is this asked in interviews?

J.P. Morgan, Goldman Sachs, Microsoft, and Google ask this to test case-based mathematical reasoning. The key insight — that mismatched positions fall into exactly two types ("xy" mismatch and "yx" mismatch) — and the observation that pairs of the same type can be resolved in one swap while a mixed pair requires two swaps, reveals clean combinatorial thinking. The math, string, and greedy interview pattern is directly demonstrated.

Algorithmic pattern used

Greedy counting. Scan through both strings simultaneously. Collect positions where they differ: count xy pairs (s1[i]='x', s2[i]='y') and yx pairs (s1[i]='y', s2[i]='x'). Each pair of xy mismatches resolves with 1 swap. Each pair of yx mismatches resolves with 1 swap. If one mismatch type has an odd leftover along with the other, they pair together at a cost of 2 swaps. If the total mismatches can't be resolved evenly, return -1.

Example explanation

s1 = "xx", s2 = "yy".

• Position 0: s1='x', s2='y' → xy mismatch. Count_xy = 1.
• Position 1: s1='x', s2='y' → xy mismatch. Count_xy = 2. Two xy mismatches → 1 swap resolves both. Total = 1 swap.

s1 = "xy", s2 = "yx".

• Position 0: xy mismatch. Count_xy = 1.
• Position 1: yx mismatch. Count_yx = 1. One xy + one yx → 2 swaps needed. Total = 2 swaps.

Common mistakes candidates make

• Trying to simulate actual swaps instead of counting mismatch types.
• Not recognizing that positions where strings already agree are irrelevant.
• Forgetting the 2-swap cost when an xy and yx mismatch pair up.
• Missing the impossible case (odd total mismatches → return -1).

Interview preparation tip

Greedy math problems with characters often boil down to categorizing mismatches and resolving them optimally. Practice this by first enumerating all possible mismatch types (here just two), then figuring out the cheapest resolution for each category. Writing out the solution in terms of count_xy and count_yx before coding leads to a clean O(n) implementation. This problem is a great warm-up for interview rounds at Goldman Sachs and J.P. Morgan where mathematical reasoning under time pressure is tested.