C++でバイナリ文字列を交互に並べ替えるための最小スワップ回数を求めるアルゴリズム

問題概要

0と1の個数が等しく、長さが偶数のバイナリ文字列が与えられます。この文字列を「交互文字列(隣り合うどの2文字も同じ文字にならない状態)」に変換するために必要な最小のスワップ回数を求めてください。

例

例えば、str = "11110000" の場合、必要なスワップ回数は 2回 です。2回の入れ替えで "10101010" のような交互文字列に変換できます。

アルゴリズムの考え方

• 文字列の偶数インデックス(i % 2 == 0)と奇数インデックスにそれぞれ存在する「0」の個数を数えます。それぞれ evenZeroCnt、oddZeroCnt とします。
• 同様に、偶数インデックスと奇数インデックスに存在する「1」の個数も数えます。それぞれ evenOneCnt、oddOneCnt とします。
• スワップは必ず「1」と「0」の間で行われます。したがって、交互文字列が「0」で始まる場合に必要なスワップ回数は min(evenZeroCnt, oddOneCnt)、「1」で始まる場合は min(evenOneCnt, oddZeroCnt) となります。
• 最終的な答えは、この2つの候補のうち小さい方です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
    int oddZeroCnt = 0;
    int evenZeroCnt = 0;
    int oddOneCnt = 0;
    int evenOneCnt = 0;
    int n = str.length();
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
            if (str[i] == '1') {
                ++evenOneCnt;
            } else {
                ++evenZeroCnt;
            }
        } else {
            if (str[i] == '1') {
                ++oddOneCnt;
            } else {
                ++oddZeroCnt;
            }
        }
    }
    int zeroSwapCnt = min(evenZeroCnt, oddOneCnt);
    int oneSwapCnt = min(evenOneCnt, oddZeroCnt);
    return min(zeroSwapCnt, oneSwapCnt);
}
int main() {
    string str = "11110000";
    cout << "Minimum swaps = " << getMinSwaps(str) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力

Minimum swaps = 2

計算量

• 時間計算量: O(n) — 文字列を一度走査するだけで完了します。
• 空間計算量: O(1) — カウンタ用の変数のみを使用します。

このアプローチのポイントは、実際にスワップを行うことなく、位置ごとの文字の出現回数を集計するだけで答えを導出できる点です。0と1の総数が等しいという前提条件があるため、偶数位置と奇数位置のカウントには美しい対称性が成り立ち、シンプルな比較だけで最小スワップ回数が求まります。