Watch 10 video solutions for Minimum Swaps to Make Strings Equal, a medium level problem involving Math, String, Greedy. This walkthrough by Algorithms Casts has 8,221 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000s1.length == s2.lengths1, s2 only contain 'x' or 'y'.Problem Overview: You get two equal-length strings s1 and s2 containing only x and y. A swap exchanges characters between the two strings at different indices. The goal is to compute the minimum number of swaps needed to make the strings identical, or return -1 if it cannot be done.
Approach 1: Count Mismatches and Resolve by Swaps (Greedy) (Time: O(n), Space: O(1))
Scan both strings once and track mismatched pairs. Only two mismatch types matter: xy (where s1[i] = x and s2[i] = y) and yx. Two xy mismatches can be fixed with one swap, and the same applies to two yx mismatches. The tricky case occurs when one xy and one yx remain. Fixing that pair requires two swaps. The formula becomes swaps = xy/2 + yx/2 + 2*(xy%2). If the total mismatches xy + yx is odd, forming valid pairs is impossible, so return -1. This approach works because each swap resolves two symmetric mismatches. The algorithm only uses counters and a single pass over the strings. It relies on simple counting and greedy pairing, which fits well with problems involving greedy reasoning and string traversal.
Approach 2: Bit Manipulation and Lookup (Time: O(n), Space: O(1))
You can encode each mismatch pair as a small integer using bit operations. Map characters to bits (x = 0, y = 1) and combine the pair using (a << 1) | b. This produces four possible values representing xx, xy, yx, and yy. Only xy and yx contribute to the swap count, so maintain counters indexed by the encoded value. After processing the entire string, apply the same pairing logic used in the greedy approach: resolve pairs of identical mismatches first, then handle the leftover cross pair requiring two swaps. Bit encoding avoids string comparisons and can slightly simplify branching logic in tight loops. This technique is common when solving character-pair problems using math and bit tricks.
Recommended for interviews: The mismatch-count greedy solution is the one interviewers expect. It shows you recognize the structure of the problem and reduce it to counting two mismatch types. The bit-manipulation variant is a neat optimization, but the core insight remains the same: mismatches must be paired, and the final cross pair costs two swaps.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count mismatches and greedy pairing | O(n) | O(1) | Best general solution. Simple logic, minimal memory, ideal for interviews. |
| Bit manipulation with encoded pairs | O(n) | O(1) | Useful when implementing compact mismatch tracking or optimizing comparisons. |