Problem: Given two strings consisting of characters ‘x’ and ‘y’, you can swap any two letters that belong to different strings. Find and return the minimum number of swaps necessary to make two strings equal. If it is not possible to make strings equal, return -1.

Constraints:

• The length of a string is between 1 and 100
• The length of two strings is the same.
• The strings only contain the letters ‘x’ and ‘y’.

Initial thought process

Let us start by making some observations. To being with, it is not actually required to swap the letters. We simply need to count the number of swaps necessary to make the string equal. Therefore, a possible strategy is to walk the strings, and count the number of swaps necessary by following some general rules. The key to the solution, then, is to find those rules. Considering some simplified cases will help us arrive at some general rules.

(Case 1) Impossible

Let us consider ‘xy’ and ‘xx’. No matter how many swaps we make, it is not possible to make those strings equal.

(Case 2) One swap

Let us consider ‘yy’ and ‘xx’. We can make the strings equal by swapping s1[0] and s2[1].

(Case 3) Two swaps

Let us consider ‘xy’ and ‘yx’. We can make the strings equal with two swaps. One way is to swap s1[0] and s2[0], and then swap s1[0] and s2[1].

Rules

If we find a mismatch where s1 has x and s2 has y, there are two strategies to resolve the mismatch.

1. Find another mismatch where s1 has x and s2 has y. We can resolve those mismatches with one exchange.
2. Find another mismatch where s1 has y and s2 has x. We can resolve those mismatches with two exchanges.

Why?

• An example of the first strategy is a situation: s1 = xx and s2 = yy (case 2). We swap s1[0] with s2[1] to make both strings equal to yx.
• An example of the second strategy is a situation s1 = xy and s2 = yx (case 3). We swap s1[0] with s2[0], then s1[0] with s2[1] to make both strings equal to xy.

Solution

With these two rules in mind, let us count the number of two different mismatches: (1) a mismatch where s1 has x, and (2) a mismatch where s1 has y. Then, we can try to resolve the mismatches by applying the first rule, then the second rule if necessary. If a mismatch remains at the end, we know that it is impossible to make the strings equal (case 1). The order of exchange is not important. Therefore we can simply count and use the counts to resolve the mismatches.

With this in mind, we arrive at the following solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    private static final int NO_SOLUTION = -1;

    public int minimumSwap(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        // validate the input
        if (n != m) {
            throw new IllegalArgumentException("The strings must be equal in length.");
        }

        int xmis = 0;  // mismatch where s1[i] has 'x'
        int ymis = 0;  // mismatch where s1[i] has 'y'

        // count mismatches
        for (int i = n-1; i >= 0; i--) {
            if (s1.charAt(i) == 'x' && s2.charAt(i) == 'y') {
                xmis++;
            } else if (s1.charAt(i) == 'y' && s2.charAt(i) == 'x') {
                ymis++;
            }
        }

        // impossible
        // (1) there should be even numbers of those types of exchanges, in which
        // the first rule suffices. OR
        // (2) there should be odd numbers of those types of exchanges, in which
        // we apply the fisrt rule then we apply the second rule once at the end.
        if (xmis % 2 != ymis % 2) {
            return NO_SOLUTION;
        }

        int numSwaps = xmis / 2 + ymis / 2; // apply the first rule
        if (xmis % 2 == 1) {
            numSwaps += 2; // if a mismatch remains, we apply the second rule
        }

        return numSwaps;
    }
}

While this question clarifies that you should return -1 in case a solution does not exist, an interview question is often not always that specific on how to handle edge cases. You will probably be responsible for clarifying how to handle the situation in which no solution exists, or whether a solution always exists at all.

Complexity

We loop through the strings once. Therefore, the time complexity is O(N) where N is the length of s1 and s2. The space complexity is O(1) because we use a constant amount of memory regardless of the input size.

Validation

The validation can be extended to verify the other contrasts of the inputs. We can clarify with the interviewer about how to handle invalid inputs. For example, we can throw an exception, or return -1, indicating no solution is possible. Furthermore, the question is often ambiguous about the constraints of the input. It is your responsibility to clarify them in an interview setting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    private static final int NO_SOLUTION = -1;
    private static final int STR_LEN_MIN = 1;
    private static final int STR_LEN_MAX = 1000;

    public int minimumSwap(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        // validate the input
        if (n != m) {
            throw new IllegalArgumentException("The strings must be equal in length.");
        }

        validateString(s1);
        validateString(s2);

        // ...
    }

    private void validateString(String str) {
        if (str.length() < STR_LEN_MIN || str.length() > STR_LEN_MAX) {
            throw new IllegalArgumentException(
                String.format(
                    "A string length must be between %d and %d",
                    STR_LEN_MIN,
                    STR_LEN_MAX
                )
            );
        }

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != 'x' && str.charAt(i) != 'y') {
                throw new IllegalArgumentException(
                    "A string must only contain characters 'x' and 'y'."
                );
            }
        }
    }

Note that validateString does not change the complexity of the solution.

Follow-ups

Swap letters in the same string

How will the solution change, if we can swap letters belonging to the same string? In this situation, case 3 in our observation will take one, rather than two, swaps to resolve. Concretely, suppose ‘xy’ and ‘yx’. Then, we can simply swap s1[0] and s1[1] to make the strings equal. In effect, we are able to resolve any two mismatches with a single swap.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minimumSwap(String s1, String s2) {
        // ...

        int numSwaps = xmis / 2 + ymis / 2; // apply the first rule
        if (xmis % 2 == 1) {
            numSwaps++; // if a mismatch remains, we apply the second rule
        }

        return numSwaps;
    }
}

An additional letter ‘z’

How will we extend the solution if the strings can contain an additional letter, say, ‘z’? In this case, the underlying mechanics of the solution does not change. Rather, we we will need to be more specific about the kind of mismatches, and extend our rules. Specifically, we need to count 6 different kinds of mismatches:

• “xy mismatch” where s1 has ‘x’ and s2 has ‘y’.
• “xz mismatch” where s1 has ‘x’ and s2 has ‘z’.
• “yx mismatch” where s1 has ‘y’ and s2 has ‘x’.
• “yz mismatch” where s1 has ‘y’ and s2 has ‘z’.
• “zx mismatch” where s1 has ‘z’ and s2 has ‘x’.
• “zy mismatch” where s1 has ‘z’ and s2 has ‘y’.

Then, our rules should be extended as follows:

For an “xy mismatch”,

1. if there is another “xy mismatch”, we can resolve those mismatched with one exchange.
2. if there is another “yx mismatch”, we can resolve those mismatched with two exchanges.

For an “xz mismatch”,

1. if there is another “xz mismatch”, we can resolve those mismatched with one exchange.
2. if there is another “zx mismatch”, we can resolve those mismatched with two exchanges.

And so on, for the rest of the mismatch types. Then, we simply apply those rules based on the count of the mismatches of each types.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Solution {
    private static final int NO_SOLUTION = -1;

    public int minimumSwap(String s1, String s2) {
        // ...

        int xyMis = 0;  // mismatch where s1[i] has 'x' and s2[i] ahs 'y'
        int xzMis = 0;  // mismatch where s1[i] has 'x' and s2[i] ahs 'z'
        int yxMis = 0;  // mismatch where s1[i] has 'y' and s2[i] ahs 'x'
        int yzMis = 0;  // mismatch where s1[i] has 'y' and s2[i] ahs 'z'
        int zxMis = 0;  // mismatch where s1[i] has 'z' and s2[i] ahs 'x'
        int zyMis = 0;  // mismatch where s1[i] has 'z' and s2[i] ahs 'y'

        // count mismatches
        for (int i = n-1; i >= 0; i--) {
            char s1Char = s1.charAt(i);
            char s2Char = s2.charAt(i);

            if (s1Char == 'x' && s2Char == 'y') {
                xyMis++;
            } else if (s1Char == 'x' && s2Char == 'z') {
                xzMis++;
            } else if (s1Char == 'y' && s2Char == 'x') {
                yxMis++;
            } else if (s1Char == 'y' && s2Char == 'z') {
                yzMis++;
            } else if (s1Char == 'z' && s2Char == 'x') {
                zxMis++;
            } else if (s1Char == 'z' && s2Char == 'y') {
                zyMis++;
            }
        }

        // Apply the rule of "one swap."
        int numSwaps = xyMis / 2 + xzMis / 2
                        + yxMis / 2 + yzMis / 2
                        + zxmis / 2 + xyMis / 2;

        // No solution is possible if there is a mismatch without its counterpart.
        if (
            (xyMis % 2 != yxmis % 2) ||
            (xzMis % 2 != zxmis % 2) ||
            (yzMis % 2 != zymis % 2)
        ) {
            return NO_SOLUTION;
        }

        if (xyMis % 2 == 1) {
            // if a mismatch remains, we apply the rule of "two swaps."
            numSwaps += 2;
        }
        if (xzMis % 2 == 1) {
            // if a mismatch remains, we apply the rule of "two swaps."
            numSwaps += 2;
        }
        if (yzMis % 2 == 1) {
            // if a mismatch remains, we apply the rule of "two swaps."
            numSwaps += 2;
        }

        return numSwaps;
    }
}

The complexity of the solution does not change because we are still looping through the strings once, counting mismatches. Here, we observe the value of deriving general rules for the solution. To handle an additional character, we could simply extend the rules and update the solution accordingly.

Lessons learned

1. When a question asks to find the number of operations, you don’t necessarily have to perform those operations. For instance, if we actually swapped the characters from the strings, the solution would be more complicated and have worse complexity.
2. Derive general rules for the solution by examining simplified cases.
3. When manipulating strings, it helps to draw a table and observe the behaviour as you iterate through them.