Skip to content

1247. Minimum Swaps to Make Strings Equal 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int minimumSwap(string s1, string s2) {
    // ("xx", "yy") = (2 "xy"s) -> 1 swap
    // ("yy", "xx") = (2 "yx"s) -> 1 swap
    // ("xy", "yx") = (1 "xy" and 1 "yx") -> 2 swaps
    int xy = 0;  // the number of indices i's s.t. s1[i] = 'x' and s2[i] 'y'
    int yx = 0;  // the number of indices i's s.t. s1[i] = 'y' and s2[i] 'x'

    for (int i = 0; i < s1.length(); ++i) {
      if (s1[i] == s2[i])
        continue;
      if (s1[i] == 'x')
        ++xy;
      else
        ++yx;
    }

    if ((xy + yx) % 2 == 1)
      return -1;
    return xy / 2 + yx / 2 + (xy % 2 == 0 ? 0 : 2);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int minimumSwap(String s1, String s2) {
    // ("xx", "yy") = (2 "xy"s) -> 1 swap
    // ("yy", "xx") = (2 "yx"s) -> 1 swap
    // ("xy", "yx") = (1 "xy" and 1 "yx") -> 2 swaps
    int xy = 0; // the number of indices i's s.t. s1[i] = 'x' and s2[i] 'y'
    int yx = 0; // the number of indices i's s.t. s1[i] = 'y' and s2[i] 'x'

    for (int i = 0; i < s1.length(); ++i) {
      if (s1.charAt(i) == s2.charAt(i))
        continue;
      if (s1.charAt(i) == 'x')
        ++xy;
      else
        ++yx;
    }

    if ((xy + yx) % 2 == 1)
      return -1;
    return xy / 2 + yx / 2 + (xy % 2 == 0 ? 0 : 2);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def minimumSwap(self, s1: str, s2: str) -> int:
    # ('xx', 'yy') = (2 'xy's) . 1 swap
    # ('yy', 'xx') = (2 'yx's) . 1 swap
    # ('xy', 'yx') = (1 'xy' and 1 'yx') . 2 swaps
    xy = 0  # the number of indices i's s.t. s1[i] = 'x' and s2[i] 'y'
    yx = 0  # the number of indices i's s.t. s1[i] = 'y' and s2[i] 'x'

    for a, b in zip(s1, s2):
      if a == b:
        continue
      if a == 'x':
        xy += 1
      else:
        yx += 1

    if (xy + yx) % 2 == 1:
      return -1
    return xy // 2 + yx // 2 + (0 if xy % 2 == 0 else 2)