C++でバイナリ文字列における0と1の個数差の最大値を求める方法

この記事では、与えられたバイナリ文字列（「0」と「1」のみで構成される文字列）から部分文字列を取り出し、その中に含まれる「0」の個数と「1」の個数の差の最大値を求める方法を解説します。

問題の確認

具体例を使って、何をすべきかを見ていきましょう。

入力

str = "100100110"

出力

3

説明

位置1〜5に対応する部分文字列「00100」には「0」が4個、「1」が1個含まれているため、差は 4 − 1 = 3 となります。これが求められる最大値です。

入力

str = "00000"

出力

5

説明

文字列がすべて「0」で構成されている場合は、文字列全体を選ぶことで差は5になります。

アルゴリズムの考え方

この問題は、「0」を +1 、「1」を −1 に置き換えて数列に変換したうえで、その最大部分配列和（Kadaneのアルゴリズムと同じ発想）を求める問題に帰着できます。「0」が多い区間ほど値は大きくなり、「1」が多い区間ほど値は小さくなるためです。

以下のプログラムでは、メモ化再帰を用いてこの値を効率よく計算しています。

プログラムの処理手順

• main() 関数内でバイナリ文字列を格納する string 型変数 str を作成し、文字列のサイズを格納する int 型変数 size を初期化して、両方を Max() 関数に渡します。

• Max() 関数では、まず One() 関数を呼び出して、すべての要素が「1」であるかどうかを判定します。

• bool 型の One() 関数を作成し、内部で int 型変数 O = 0 を用意します。

• i = 0 から str.size() 未満までループし、str[i] が '1' であれば変数 O に 1 を加算します。

• ループを抜けた後、O == size が成立していれば true を返します。

• Max() 関数に戻り、One() が true を返した場合は答えとして -1 を返します（すべて「1」の場合は「0」の個数が常に少なくなるため）。

• それ以外の場合は各区間の差の計算へ進みます。配列 int a[100] = { 0 } を初期化します。

• i = 0 から size 未満までループし、a[i] = (str[i] == '0' ? 1 : -1) として文字列の各要素を数値に変換します。

• ループの外でもう一つの配列 int arr[100][3] を用意し、memset(arr, -1, sizeof arr) ですべての要素を -1 で初期化した後、Length(a, str, size, 0, 0, arr) を呼び出します。

• Length() 関数では、最初に i >= size かどうかを判定します。真であれば文字列を読み終えたことを意味するので 0 を返します。

• 次に arr[i][s] != -1 かどうかを判定します。真であれば、その状態はすでに計算済みなので、記憶しておいた arr[i][s] の値をそのまま返します（メモ化）。

• s == 0 の場合は、arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), Length(a, str, size, i + 1, 0, arr)) を返します。これは「現在の位置から部分文字列を始めるか」「次の位置へスキップするか」を選択することに相当します。

• それ以外の場合（部分文字列の選択中）は、arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), 0) を返し、区間の合計が負になった時点で切り捨てます。

C++実装例

#include <bits/stdc++.h>
using namespace std;
bool One(string str, int size){
    int O = 0;
    for (int i = 0; i < str.size(); i++)
        O += (str[i] == '1');
    return (O == size);
}
int Length(int a[], string str, int size,
int i, int s, int arr[][3]){
    // 文字列を読み終えた場合
    if (i >= size)
        return 0;
    // すでに計算済みの場合（メモ化）
    if (arr[i][s] != -1)
        return arr[i][s];
    if (s == 0)
        return arr[i][s] = max(a[i] +
        Length(a, str, size, i + 1, 1, arr),
        Length(a, str, size, i + 1, 0, arr));
    else
        return arr[i][s] = max(a[i] +
        Length(a, str, size, i + 1, 1, arr), 0);
}
int Max(string str, int size){
    // すべての要素が「1」かどうかを確認
    if (One(str, size))
        return -1;
    // 各区間の差を計算
    int a[100] = { 0 };
    for (int i = 0; i < size; i++)
        a[i] = (str[i] == '0' ? 1 : -1);
    int arr[100][3];
    memset(arr, -1, sizeof arr);
    return Length(a, str, size, 0, 0, arr);
}
// main関数
int main(){
    string str = "100100110";
    int size = 9;
    cout << Max(str, size);
    return 0;
}

出力

3

計算量について

メモ化により各状態 (i, s) は一度しか計算されないため、時間計算量は文字列の長さを N として O(N)、メモテーブルと再帰スタックのため空間計算量も O(N) となります。これにより、単純な全探索（O(N²)）よりも効率的に答えを求められます。