C++で文字列を単調増加にするための最小反転回数を求める方法

問題の概要

'0'と'1'のみから構成される文字列が与えられたとします。この文字列が「単調増加」であるとは、いくつかの'0'（0個でも可）の後に、いくつかの'1'（これも0個でも可）が続く形になっている状態を指します。

ここで、'0'と'1'からなる文字列Sが与えられ、任意の'0'を'1'に、または'1'を'0'に反転（フリップ）できるものとします。このとき、Sを単調増加な文字列にするために必要な最小の反転回数を求めるのが本問題です。

例えば、入力が「010110」の場合、出力は2になります。反転を2回行うことで、「011111」または「000111」という単調増加な文字列を得ることができるためです。

解法のアプローチ

この問題は、貪欲法（グリーディ法）を用いて1回の走査で解くことができます。基本的な考え方は以下の通りです。

• これまでに登場した'1'の個数をoneCountとして記録します。
• ある'1'の後に'0'が出現した場合、「その'0'を'1'に反転する」か「それまでの'1'をすべて'0'に反転する」かの2択があります。
• '0'が出現するたびにflipCountを1増やしますが、もしoneCount（それまでの'1'の数）の方がflipCountより小さければ、すべての'1'を'0'に反転する方がコストが低いため、flipCountをoneCountに置き換えます。

具体的な手順は以下の通りです。

• n := Sのサイズとし、flipCount := 0、oneCount := 0 で初期化します。
• i を 0 から n-1 まで繰り返します。
  • S[i] が '0' の場合：
    • oneCount が 0 であれば、先頭の'0'は反転不要なので次の反復へスキップします。
    • そうでなければ flipCount を 1 増やします。
  • それ以外（S[i] が '1'）の場合は、oneCount を 1 増やします。
  • oneCount < flipCount であれば、flipCount := oneCount と更新します。
• 最後に flipCount を返します。

このアルゴリズムの計算量はO(n)であり、文字列を1回走査するだけで答えが求まるため、非常に効率的です。

C++による実装例

以下に、上記のアルゴリズムを実装したC++のコードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minFlipsMonoIncr(string S) {
        int n = S.size();
        int flipCount = 0;
        int oneCount = 0;
        for(int i = 0; i < n; i++){
            if(S[i] == '0'){
                if(oneCount == 0) continue;
                flipCount++;
            } else oneCount++;
                if(oneCount < flipCount) flipCount = oneCount;
        }
        return flipCount;
    }
};
main(){
    Solution ob;
    cout << (ob.minFlipsMonoIncr("010110"));
}

入力

"010110"

出力

2

まとめ

本問題では、貪欲法を用いることで、文字列を1回走査するだけで最小反転回数を求めることができました。各時点で「'0'を'1'に反転するコスト」と「それまでの'1'をすべて'0'に反転するコスト」を比較し、常に小さい方を採用することが最適解につながります。時間計算量O(n)、空間計算量O(1)という非常に効率的な解法です。