C++でバイナリ文字列から部分文字列「010」を削除する最小ステップ数を求める方法

問題概要

バイナリ文字列が与えられたとき、その文字列から部分文字列「010」を削除するために必要な最小のステップ数を求めるのが課題です。ここでいう1ステップとは、文字列内の任意の1文字を「0」から「1」へ(またはその逆へ)変更する操作を指します。

例

入力文字列が「010010」の場合、必要なステップ数は2です。

• 最初の「0」を「1」に変更します。文字列は「110010」になります。
• 最後の「0」を「1」に変更します。最終的な文字列は「110011」になり、「010」というパターンが完全に消えます。

アルゴリズム

1. 文字列をインデックス0からn-2まで走査する
2. 連続する3文字が「0」「1」「0」の並びになっている場合、いずれか1文字を変更すればよい
   カウントを1増やし、ループカウンターを2進める(重複カウントを防ぐため)

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int getMinSteps(string str) { 
    int cnt = 0;
    for (int i = 0; i < str.length() - 2; ++i) {
        if (str[i] == '0' && str[i + 1] == '1' && str[i + 2] == '0') {
            ++cnt;
            i += 2;
        }
    }
    return cnt;
}
int main() {
    string str = "010010";
    cout << "Minimum required steps = " << getMinSteps(str)
    << endl;
    return 0;
}

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

出力

Minimum required steps = 2

アルゴリズムのポイント

「010」というパターンを見つけた場合、その3文字のうちどれか1文字を変更するだけでパターンを崩せます。パターンを検出した後にループカウンターを2進めることで、すでに処理済みの文字を再び走査するのを避け、効率よくカウントできます。

この手法により、文字列全体を一度の走査で処理できるため、時間計算量はO(n)、追加の記憶域はカウンターのみで空間計算量はO(1)となります。長いバイナリ文字列に対しても高速に動作する実用的なアプローチです。