C++で文字列を等しくするための最小スワップ回数を求めるアルゴリズム

問題概要

「x」と「y」のみで構成された、同じ長さの2つの文字列 s1 と s2 が与えられます。目標は、これらの文字列を互いに等しくすることです。操作としては、異なる文字列に属する任意の2文字を入れ替えることができます。つまり、s1[i] と s2[j] をスワップします。s1 と s2 を等しくするために必要な最小のスワップ回数を求め、どうしても不可能な場合は -1 を返してください。

例えば、s1 = "xy"、s2 = "yx" の場合、答えは 2 になります。まず s1[0] と s2[0] をスワップすると、s1 = "yy"、s2 = "xx" となります。次に s1[0] と s2[1] をスワップすると、s1 = "xy"、s2 = "xy" となり、両方の文字列が一致します。

解決アプローチ

この問題は、位置ごとの文字の不一致を分類してカウントすることで効率的に解けます。考え方は以下の通りです。

• x1、x2、y1、y2 をすべて 0 で初期化します
• i を 0 から s1 の長さまで順に処理します
  • a := s1[i]、b := s2[i] とします
  • a と b が異なる場合（不一致の位置）
    • a が「x」なら x1 を、そうでなければ y1 をインクリメントします
    • b が「x」なら x2 を、そうでなければ y2 をインクリメントします
• (x1 + x2) が奇数、または (y1 + y2) が奇数の場合は -1 を返します
• x1 / 2 + y1 / 2 + (x1 % 2) × 2 を返します

なぜこの計算で求まるのか

不一致の位置では、必ず「xy」（s1がx、s2がy）か「yx」（s1がy、s2がx）のペアになります。同じ種類のペア2つを1回のスワップで同時に解消できるため、「xy」のペアには x1 / 2 回、「yx」のペアには y1 / 2 回のスワップで対応できます。片方だけ余った場合は、異種ペア間で2回のスワップが必要になるため、(x1 % 2) × 2 を加算します。また、x と y の総数が奇数になると文字数の整合性が取れなくなるため、その場合は -1 を返します。

C++での実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
        for(int i = 0; i < s1.size(); i++){
            char a = s1[i];
            char b = s2[i];
            if(a != b){
                if(a == 'x')x1++;
                else y1++;
                if(b == 'x')x2++;
                else y2++;
            }
        }
        if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
        return x1/2 + y1/2 + (x1 % 2) * 2;
    }
};
main(){
    Solution ob;
    cout <<ob.minimumSwap("xy", "yx");
}

入力

"xy"
"yx"

出力

2

まとめ

このアルゴリズムは、文字列を一度走査して不一致箇所を分類・集計するだけで答えが求まるため、時間計算量は O(n)、空間計算量は O(1) と非常に効率的です。貪欲法の考え方を応用した良い例と言えるでしょう。