Formatted question description: https://leetcode.ca/all/1247.html

1247. Minimum Swaps to Make Strings Equal

Level

Medium

Description

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 can’t 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

Example 4:

Input: s1 = “xxyyxyxyxx”, s2 = “xyyxyxxxyx”

Output: 4

Constraints:

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

Solution

Loop over s1 and s2 and find the indices where the characters in s1 and s2 are different. Use two lists difX and difY to store the indices where the character in s1 is 'x' and the character in s2 is 'y', and the indices where the character in s1 is 'y' and the character in s2 is 'x', respectively.

Calculate sizeX = difX.size() and sizeY = difY.size(). If sizeX + sizeY is odd, then it is impossible to swap the characters to make the two strings equal, so return -1. If sizeX + sizeY is even, then sizeX and sizeY are both even or both odd. If both even, then return (sizeX + sizeY) / 2. If both odd, then return (sizeX + sizeY) / 2 + 1.

The explanation on the return value is as follows.

If sizeX and sizeY are both even, then for the sizeX indices where the character in s1 is 'x' and the character in s2 is 'y', let indices1 and indices2 are two disjoint subsets of difX such that indices1 and indices2 have equal number of elements and the union of indices1 and indices2 equals difX. Replace each character in s1 at indices from indices1 with each character in s2 at indices from indices2. Do the same for the other sizeY indices as well. Thus the total number of swaps is (sizeX + sizeY) / 2.
If sizeX and sizeY are both odd, then perform the steps above for sizeX - 1 indices from difX and sizeY - 1 indices from difY, and the total numbers of swaps is (sizeX + sizeY) / 2 - 1 so far. After that, there are two indices left, where the subsequences are "xy" and "yx" in s1 and s2, respectively. To make the subsequences equal, two swaps are needed. Thus the total number of swaps is (sizeX + sizeY) / 2 + 1.

class Solution {
    public int minimumSwap(String s1, String s2) {
        List<Integer> difX = new ArrayList<Integer>();
        List<Integer> difY = new ArrayList<Integer>();
        int length = s1.length();
        for (int i = 0; i < length; i++) {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            if (c1 != c2) {
                if (c1 == 'x')
                    difX.add(i);
                else
                    difY.add(i);
            }
        }
        int sizeX = difX.size(), sizeY = difY.size();
        if ((sizeX + sizeY) % 2 != 0)
            return -1;
        else if (sizeX % 2 == 0)
            return (sizeX + sizeY) / 2;
        else
            return (sizeX + sizeY) / 2 + 1;
    }
}

// OJ: https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minimumSwap(string a, string b) {
        int x = 0, y = 0, ans = 0;
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] == b[i]) continue;
            if (a[i] == 'x') ++x;
            else ++y;
            if (x == 2) ++ans, x = 0;
            if (y == 2) ++ans, y = 0;
        }
        if (x != y) return -1;
        return x ? ans + 2 : ans;
    }
};

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy = yx = 0
        for a, b in zip(s1, s2):
            xy += a < b
            yx += a > b
        if (xy + yx) % 2:
            return -1
        return xy // 2 + yx // 2 + xy % 2 + yx % 2

############

# 1247. Minimum Swaps to Make Strings Equal
# https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        counter1, counter2 = Counter(s1), Counter(s2)
        
        if (counter1["x"] + counter2["x"]) % 2 and (counter1["y"] + counter2["y"]) % 2: return -1
        
        mp1, mp2 = Counter(), Counter()
        
        res = 0
        
        for c1,c2 in zip(s1,s2):
            if c1 != c2:
                if mp1[c1] > 0 and mp2[c2] > 0:
                    mp1[c1] -= 1
                    mp2[c2] -= 1
                else:
                    mp1[c1] += 1
                    mp2[c2] += 1
                    res += 1
        
        return res

func minimumSwap(s1 string, s2 string) int {
	xy, yx := 0, 0
	for i := range s1 {
		if s1[i] < s2[i] {
			xy++
		}
		if s1[i] > s2[i] {
			yx++
		}
	}
	if (xy+yx)%2 == 1 {
		return -1
	}
	return xy/2 + yx/2 + xy%2 + yx%2
}

var minimumSwap = function (s1, s2) {
    let xy = 0,
        yx = 0;
    for (let i = 0; i < s1.length; ++i) {
        const a = s1[i],
            b = s2[i];
        if (a < b) {
            ++xy;
        }
        if (a > b) {
            ++yx;
        }
    }
    if ((xy + yx) % 2 === 1) {
        return -1;
    }
    return Math.floor(xy / 2) + Math.floor(yx / 2) + (xy % 2) + (yx % 2);
};

1247 - Minimum Swaps to Make Strings Equal

1247. Minimum Swaps to Make Strings Equal

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1247. Minimum Swaps to Make Strings Equal

Level

Description

Solution

All Problems

All Solutions