C++で文字列を「ab」フリーにするために必要な操作回数を求めるアルゴリズム

問題の概要

「a」と「b」のみで構成される文字列が与えられ、その文字列から「ab」という並びをすべて取り除くために必要な操作回数を求めるのが課題です。使用できる操作は「文字列中の ab を bba に置き換える」ことだけです。まず文字列に「ab」が含まれているかどうかを確認し、含まれている場合は置き換えを繰り返して、最終的に「ab」が一切現れない状態（abフリー）にします。

入出力例

例1

入力: str = "ababaa"

出力: 文字列を「ab」フリーにするために必要な操作回数: 4

説明: 文字列「ababaa」に対して、最初の「ab」を「bba」に置き換えると「bbaabaa」になります（1回目）。続けて次の「ab」を「bba」に置き換えると「bbabbaaa」になります（2回目）。さらに残った「ab」を順に置き換えていくと、すべての「b」が「a」よりも左側に移動し、「ab」が存在しない状態になります。合計の操作回数は4回です。

例2

入力: str = "abaa"

出力: 文字列を「ab」フリーにするために必要な操作回数: 1

説明: 「abaa」に含まれる「ab」は1箇所だけです。「ab」を「bba」に置き換えると「bbaaa」となり、これ以上「ab」は現れません。したがって操作回数は1回です。

アルゴリズムの考え方

実際に置き換えを繰り返して文字列をシミュレートすると非効率になるため、文字列を右端から先頭へ向かって1文字ずつ走査することで、操作回数を直接計算できます。

• 文字列とその長さを受け取り、処理を行う関数を用意します。
• 操作回数を格納する変数 count と、走査済みの範囲に含まれる「b」の個数を表す変数 total を0で初期化します。
• 文字列を右端から順に走査します。
• 注目している文字が「b」の場合は、total を1増やします（現在位置より右側にある「b」の総数が1つ増えたことを意味します）。
• 注目している文字が「a」の場合は、その右側にある total 個の「b」とそれぞれ「ab」のペアを形成するため、count に total を加算します。また、各「ab」を「bba」に置き換えるたびに「b」が2倍に増えるため、total を2倍に更新します。
• 走査が完了した時点の count の値が答えとなります。

この手法により、置き換えを実際に行わなくても O(n) の時間計算量で答えを求めることができます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int operations_ab_free(string str, int len){
    int count = 0;
    char arr[len + 1];
    strcpy(arr, str.c_str());
    int total = 0;
    for (int i = 0; i < len; i++){
        if (arr[len - i - 1] == 'a'){
            count = (count + total);
            total = (total * 2);
        }
        else{
            total++;
        }
    }
    return count;
}
int main(){
    string str = "ababaa";
    int length = str.length();
    cout << "Count of operations to make a binary string \"ab\" free are: " << operations_ab_free(str, length) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

Count of operations to make a binary string "ab" free are: 4