Leetcode 1247. Minimum Swaps to Make Strings Equal

Problem Explanation:

Given two strings s1 and s2, each of which only contains the characters 'x' or 'y', the task is to make these two strings identical to each other by conducting swaps of characters between s1 and s2. Based on the problem constraints, only two characters that belong to different strings (s1[i] and s2[j]) are allowed to be swapped. The goal is to return the minimum number of swaps required to make the two strings equal to each other. If it is impossible, -1 should be returned.

Let's understand this with an example:

1
2python
3s1 = "xx", s2 = "yy"

Here, we can make s1 and s2 the same by swapping s1[0] and s2[1], resulting in s1 = "yx" and s2 = "yx". Thus, the minimum number of swaps required is 1.

Solution Approach:

The problem can be solved by counting the occurrences of 'x' and 'y' characters in odd indexes and even indexes separately. Two scenarios arise:

  • If a character 'x' in s1 is mismatched with a character 'yins2, indicate it as 'xy'`.
  • Likewise, if a character 'y' in s1 is mismatched with a character 'x' in s2, indicate it as 'yx'.

We then just need to calculate the number of swaps:

  • Two 'xy' or two 'yx' mismatches can be resolved by 1 swap. Thus, the total number of swaps is xy/2 + yx/2.
  • If the number of 'xy' mismatches is odd, 2 more swaps will be required.
  • If the total number of mismatches is odd, it's impossible to resolve.

Python Solution:

1
2python
3class Solution:
4    def minimumSwap(self, s1: str, s2: str) -> int:
5        xy, yx = 0, 0
6        for c1, c2 in zip(s1, s2): 
7            if c1 != c2:
8                if c1 == 'x': 
9                    xy += 1
10                else: 
11                    yx += 1
12        # If total mismatches is odd it's impossible
13        if (xy + yx) % 2: 
14            return -1
15        # Either swap 2 'xy' or 'yx' or swap both 'xy' and 'yx'.
16        return xy // 2 + yx // 2 + (xy % 2) * 2

Java Solution:

1
2java
3class Solution {
4    public int minimumSwap(String s1, String s2) {
5        int xy = 0, yx = 0;
6        for (int i = 0; i < s1.length(); ++i) {
7            if (s1.charAt(i) == s2.charAt(i)) 
8                continue;
9            if (s1.charAt(i) == 'x') 
10                ++xy;
11            else 
12                ++yx;
13        }
14        if ((xy + yx) % 2 == 1)
15            return -1;
16        return xy / 2 + yx / 2 + (xy % 2 == 1 ? 2 : 0);
17    }
18}

JavaScript Solution:

1
2javascript
3var minimumSwap = function(s1, s2) {
4    let xy = 0, yx = 0;
5    for (let i = 0; i < s1.length; i++) {
6        if (s1.charAt(i) != s2.charAt(i)) {
7            if(s1.charAt(i) == 'x') 
8                xy++;
9            else 
10                yx++;
11        }
12    }
13    if ((xy+yx) % 2 == 1)
14        return -1;
15    return (xy >> 1) + (yx >> 1) + ((yx % 2 == 1) ? 2 : 0);
16};

C++ Solution:

1
2c++
3class Solution {
4public:
5    int minimumSwap(string s1, string s2) {
6        int xy = 0, yx = 0;
7        for (int i=0; i<s1.length(); i++) {
8            if(s1[i] == s2[i]) 
9                continue;
10            if(s1[i] == 'x') 
11                ++xy;
12            else 
13                ++yx;
14        }
15        if ((xy + yx) % 2 == 1) 
16            return -1;
17        return xy / 2 + yx / 2 + (xy % 2 == 1 ? 2 : 0);
18    }
19};

C# Solution:

1
2csharp
3public class Solution {
4    public int MinimumSwap(string s1, string s2) {
5        int xy = 0, yx = 0;
6        for (int i = 0; i < s1.Length; i++) {
7            if (s1[i] == s2[i]) 
8                continue;
9            if (s1[i] == 'x') 
10                ++xy;
11            else 
12                ++yx;
13        }
14        if ((xy + yx) % 2 == 1) 
15            return -1;
16        return xy / 2 + yx / 2 + (xy % 2 == 1 ? 2 : 0);
17    }
18}

Scala Solution:

1
2scala
3object Solution {
4    def minimumSwap(s1: String, s2: String): Int = {
5        var xy = 0
6        var yx = 0
7        for(i <- 0 until s1.length) {
8            if(s1(i) != s2(i)){
9                if(s1(i) == 'x')
10                    xy += 1
11                else
12                    yx += 1
13            }
14        }
15        if((xy+yx) % 2 == 1) 
16          -1
17        else
18          xy / 2 + yx / 2 + (if(xy % 2 == 1) 2 else 0)
19    }
20}

This Scala solution uses a basic iterative approach to examine each character in the strings and increment the respective xy and yx counters. The solution then checks if the total of xy and yx is odd, returning -1 if it is, because it would be impossible to make both strings identical since there would always be one character mismatched.

Otherwise, it calculates the number of swaps required according to the established method. The / operator is used for division that discards the remainder, and the % operator obtains the remainder. For example, xy / 2 gives the number of swaps for xy pairs, and (xy % 2) * 2 provides the additional swaps needed if there is an odd number of xy.

Kotlin Solution:

1
2kotlin
3class Solution {
4    fun minimumSwap(s1: String, s2: String): Int {
5        var xy = 0
6        var yx = 0
7        for (i in s1.indices) {
8            when {
9                s1[i] == 'x' && s2[i] == 'y' -> xy++
10                s1[i] == 'y' && s2[i] == 'x' -> yx++
11            }
12        }
13        return when {
14            (xy + yx) % 2 == 1 -> -1
15            else -> xy / 2 + yx / 2 + (xy % 2) * 2
16        }
17    }
18}

This Kotlin solution uses a when expression, which is like an advanced form of switch found in other languages like Java. The when expression is both expressive and concise, particularly when we have to handle multiple conditions which decide the flow of the program.

In summary, the implementation of the solution in different programming languages follows the same logic design but varies in language syntax and features utilization. This illustrates the versatility of the algorithm and its language-independent nature.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫