C++で左側をすべて1、右側をすべて0にするための最小反転回数を求める方法

問題文

「0」と「1」からなる2進文字列が与えられます。この文字列を反転（フリップ）して、左側をすべて「1」、右側をすべて「0」にするとき、必要となる最小の反転回数を求めるのが課題です。

例

与えられた2進文字列は「0010101」です。この文字列には「1」が3個、「0」が4個含まれています。下記のように4ビットを反転することで、左側がすべて「1」、右側がすべて「0」の文字列にすることができます。

0010101

反転後の文字列は次のとおりです。

1110000

アルゴリズム

• 文字列を左から右へ走査し、各位置までの「0」をすべて「1」に変換するために必要な反転回数を累積的に計算します。
• 文字列を右から左へ走査し、各位置からの「1」をすべて「0」に変換するために必要な反転回数を累積的に計算します。
• 分割位置をすべて試し、「0の反転回数＋1の反転回数」の合計が最小となる値を求めます。

実装例（C++）

#include <iostream>
#include <string>
#include <climits>
using namespace std;

int minFlips(string binaryString) {
    int n = binaryString.length();
    int flipCnt, zeroFlips[n], oneFlips[n];

    // 左から右へ走査し、各位置までの「0」を「1」にする反転回数を記録
    flipCnt = 0;
    for (int i = 0; i < n; ++i) {
        if (binaryString[i] == '0') {
            ++flipCnt;
        }
        zeroFlips[i] = flipCnt;
    }

    // 右から左へ走査し、各位置からの「1」を「0」にする反転回数を記録
    flipCnt = 0;
    for (int i = n - 1; i >= 0; --i) {
        if (binaryString[i] == '1') {
            ++flipCnt;
        }
        oneFlips[i] = flipCnt;
    }

    // 全ての分割位置について反転回数の合計を評価し、最小値を求める
    int minFlips = INT_MAX;
    for (int i = 1; i < n; ++i) {
        int sum = zeroFlips[i - 1] + oneFlips[i];
        if (sum < minFlips) {
            minFlips = sum;
        }
    }
    return minFlips;
}

int main() {
    string binaryString = "0010101";
    cout << "Minimum flips: " << minFlips(binaryString) << endl;
    return 0;
}

計算量

このアルゴリズムは文字列を3回走査するだけで済むため、時間計算量は O(n)、補助配列2つを使用するため空間計算量も O(n) となります。文字列の長さが大きい場合でも効率的に動作します。

出力

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

Minimum flips: 4