バイナリ文字列内で0と1の個数差が最大となる部分文字列を求める方法（C++・O(n)時間）

問題の概要

与えられたバイナリ文字列（0と1のみで構成される文字列）から部分文字列を取り出し、その中に含まれる「0」の個数と「1」の個数の差が最大になる値を求めるのがこの問題の目的です。

具体的にどのような処理を行うのか、例を使って確認してみましょう。

入力例1

str = "10010110"

出力例1

2

解説

位置1から4までの部分文字列「0010」に着目すると、「0」が3個、「1」が1個含まれています。したがって個数の差は 3 − 1 = 2 となり、これがこの文字列全体から得られる最大値です。

入力例2

str = "00000"

出力例2

5

すべて「0」で構成されているため、文字列全体を部分文字列として選べば差は5となり、これが最大値になります。

アルゴリズムの考え方

この問題は、動的計画法（DP）の考え方を使うことで O(n) の計算量で効率的に解くことができます。基本的な手順は以下の通りです。

• main() 関数内でバイナリ文字列を格納する string 型変数 str を用意し、長さ str.length()+1 の int 型配列 arr を宣言します。
• memset(arr, 0, sizeof(arr)) を使って、arr[] の全要素を 0 で初期化します。
• j = 1 から j <= str.length() までループを回します。
• 各位置の文字が '1' の場合は、その文字が差を減らす方向に働くため arr[j] = max(arr[j-1] - 1, -1) とします。つまり、前の値から1引いた値と -1 の大きい方を採用し、累積和が負になった時点で新たな部分文字列を開始できるようにしています。
• 文字が '0' の場合は逆に差を増やす方向に働くため、arr[j] = max(arr[j-1] + 1, 1) とします。
• ループ終了後、*max_element(arr+1, arr+str.length()+1) を使って配列内の最大値を出力します。

ここでのポイントは、max() の第2引数として -1 や 1 を指定している点です。これにより、累積差がマイナスになったタイミングでそれ以前の部分を切り捨て、新しい部分文字列の探索を始めることができます。これは「最大部分配列和（Kadaneのアルゴリズム）」と同じ発想です。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str = "10010110";
    int arr[str.length()+1];
    memset(arr,0,sizeof(arr));
    for(int j=1;j<=str.length();j++){
        if(str[j-1]=='1')
            arr[j]=max(arr[j-1]-1,-1);
        else
            arr[j]=max(arr[j-1]+1,1);
    }
    cout<<*max_element(arr+1,arr+str.length()+1);
    return 0;
}

実行結果

2

まとめ

この手法では、各文字を走査しながら「0」なら +1、「1」なら -1 として累積差を更新し、途中で負になったらリセットするというシンプルな処理だけで、最適な部分文字列における0と1の個数差の最大値を求められます。計算量は文字列長 n に対して O(n)、追加のメモリも配列1つ分で済むため、非常に効率的なアプローチと言えます。