【C++】バイナリ文字列をk回連結したときの最大連続ゼロを求めるアルゴリズム

問題の概要

長さ n のバイナリ文字列(0と1だけで構成された文字列)と整数 k が与えられます。この文字列を k回連結したあと、連結結果の中に現れる連続する「0」の最大個数を求めるのが本記事の目的です。

たとえば、バイナリ文字列が "0010010"、k = 2 の場合、連結後の文字列は "00100100010010" となり、この中で最も長い連続する0は中央の「000」の部分、つまり 3個 です。

解法のアプローチ

この問題は、連結後の巨大な文字列を実際に作らずとも、元の文字列の性質だけから答えを導き出せます。ポイントは次の2つです。

• 文字列がすべて「0」の場合: 答えは単純に n × k になります。
• 文字列に「1」が含まれる場合: 次の2つのうち大きい方が答えになります。
  • 元の文字列内にある「0のみの部分文字列」の最大長
  • 「先頭から続く0の長さ(接頭辞)+ 末尾から続く0の長さ(接尾辞)」の合計(k > 1 のときのみ採用)

接頭辞と接尾辞を組み合わせる理由は、文字列を連結すると「前のコピーの末尾の0」と「次のコピーの先頭の0」がつながり、元の文字列には存在しないより長い0の連なりが生まれる可能性があるからです。

アルゴリズム

max_zero_count(str, n, k) −

1. total := 0、len := 0 で初期化する
2. i を 0 から n-1 まで繰り返す:
     str[i] が '0' なら len を +1、それ以外は len := 0 にリセット
     total := max(total, len)
3. total = n なら(文字列全体が0のみ)、n * k を返す
4. prefix := 先頭から続く0の最大長
   suffix := 末尾から続く0の最大長
5. k > 1 ならば、total := max(total, prefix + suffix)
6. total を返す

C++による実装例

#include <iostream>
using namespace std;

int max_length_substring(string str, int n, int k) {
    int total_len = 0;
    int len = 0;
    for (int i = 0; i < n; ++i) {
        if (str[i] == '0') // 現在の文字が0なら len をカウントアップ
            len++;
        else               // 1が出たらリセット
            len = 0;
        total_len = max(total_len, len);
    }
    if (total_len == n)    // 文字列全体が0のみの場合
        return n * k;

    int prefix = 0, suffix = 0;
    for (int i = 0; str[i] == '0'; ++i, ++prefix);     // 先頭から続く0の長さ
    for (int i = n - 1; str[i] == '0'; --i, ++suffix); // 末尾から続く0の長さ

    if (k > 1)
        total_len = max(total_len, prefix + suffix);
    return total_len;
}

int main() {
    int k = 3;
    string str = "0010010";
    int res = max_length_substring(str, str.length(), k);
    cout << "Maximum length of 0s: " << res;
}

実行結果

Maximum length of 0s: 3

入力文字列 "0010010" は先頭に「00」(接頭辞)、末尾に「0」(接尾辞)を持っています。k = 3 で連結すると、コピーの境界部分で 2 + 1 = 3 個の連続した0が生まれます。一方、文字列内部の0の最大連続長は2個なので、最終的な答えは 3 となります。

計算量

このアルゴリズムは文字列を1回走査するだけでよいため、時間計算量は O(n)、空間計算量は O(1) です。連結後の長大な文字列を実際にメモリ上に生成する必要がない点が、この手法の大きな強みです。