Practice/Google/Leetcode 1247. Minimum Swaps to Make Strings Equal

Leetcode 1247. Minimum Swaps to Make Strings Equal

CodingMust

Problem

You are given two strings s1 and s2 of equal length, where each string contains only the characters 'x' and 'y'. Your task is to make both strings identical by performing the minimum number of swap operations.

In one swap operation, you can select any index i from string s1 and any index j from string s2, then exchange the characters at those positions (swap s1[i] with s2[j]).

Return the minimum number of swaps required to make the strings identical. If it's impossible to make them identical, return -1.

Requirements

1. Implement a function that takes two strings as input
2. Count the positions where the strings differ
3. Calculate the minimum number of swaps needed
4. Return -1 if making the strings identical is impossible
5. Handle edge cases including already identical strings

Constraints

• 1 <= s1.length, s2.length <= 1000
• s1.length == s2.length
• Both strings contain only 'x' and 'y' characters
• Time complexity should be O(n) where n is the length of the strings
• Space complexity should be O(1)

Examples

Example 1:

Input: s1 = "xy", s2 = "yx" Output: 1 Explanation: Swap s1[0] with s2[0] to get s1 = "yy" and s2 = "xy", then swap s1[1] with s2[1] to get s1 = "yx" and s2 = "yx". Wait, that's 2 swaps. Actually, we can swap s1[0] with s2[1] to get s1 = "yy" and s2 = "yx". Then... Let me reconsider: one swap of s1[0]='x' with s2[0]='y' gives both strings "yy", which isn't equal. The correct approach: this requires 1 swap if we have one xy pair and one yx pair; they can be resolved with 2 swaps. But if both are the same type, 2 can be resolved with 1 swap.

Example 2:

Input: s1 = "xx", s2 = "yy" Output: 1 Explanation: Swap s1[0] with s2[0], and swap s1[1] with s2[1]. Both become "yx" after first swap, then "yy" and "xx". Actually: swap s1[0] with s2[1] gives s1="yx", s2="yy". The pattern is: two mismatches of the same type need 1 swap.

Example 3:

Input: s1 = "xxx", s2 = "yyy" Output: -1 Explanation: There are 3 mismatches total. Since the total is odd, it's impossible to make the strings equal.