【C++】aの個数がbより多い部分文字列の総数を効率的に求める方法

この問題では、文字 a と b のみで構成された文字列 str と整数 N が与えられます。str を N 回繰り返して連結することで新しい文字列を作成し、その中に含まれる「a の出現回数が b より多い」部分文字列の総数を求めて出力するのが課題です。

問題の例

まず、具体的な例で問題を確認してみましょう。

入力: aab 2
出力: 9
説明: 作成された文字列は aabaab。
条件を満たす部分文字列: 'a', 'aa', 'aab', 'aaba', 'aabaa', 'aabaab', 'aba', 'baa', 'abaa'

解法のアプローチ

この問題を解くには、毎回完全な文字列を生成するのではなく、元の文字列 str に対して先頭からのプレフィックス（接頭辞）ごとに a と b の累積出現回数を調べていくのがポイントです。以下の手順で効率的に計算できます。

• ステップ1： 元の文字列 str を走査し、各位置までの a と b の累積個数を比較して、a > b となる位置の数 count を求めます。
• ステップ2： count が 0 の場合、または n が 1 の場合は、これ以上の計算は不要です。
• ステップ3： 文字列全体で常に a > b が成り立つ場合（count == len）、あるいは a と b の総数が等しい場合（a - b == 0）は、答えは count × n として簡単に求められます。
• ステップ4： それ以外の場合は、残りの繰り返し分をシミュレートします。1 回の繰り返しで新たに加わるカウント count2 が 0 になればそれ以上増えないため処理を打ち切ることができ、逆に count2 が文字列長と一致すれば、残りの繰り返し分を一括で加算して終了できます。

C++での実装例

上記の考え方をもとにしたプログラムの実装例がこちらです。

#include <iostream>
#include <string.h>
using namespace std;
int prefixCount(string str, int n){
    int a = 0, b = 0, count = 0;
    int i = 0;
    int len = str.size();
    for (i = 0; i < len; i++) {
       if (str[i] == 'a')
           a++;
       if (str[i] == 'b')
           b++;
       if (a > b) {
       count++;
   }
}
if (count == 0 || n == 1) {
    cout<<count;
    return 0;
}
if (count == len || a - b == 0) {
    cout<<(count*n);
    return 0;
}
int n2 = n - 1, count2 = 0;
while (n2 != 0) {
    for (i = 0; i < len; i++) {
       if (str[i] == 'a')
           a++;
       if (str[i] == 'b')
           b++;
       if (a > b)
       count2++;
   }
    count += count2;
    n2--;
    if (count2 == 0)
       break;
    if (count2 == len) {
       count += (n2 * count2);
       break;
    }
    count2 = 0;
   }
    return count;
}
int main() {
    string str = "aba";
    int N = 2;
    cout<<"The string created by using '"<<str<<"' "<<N<<" times has ";
    cout<<prefixCount(str, N)<<" substring with count of a greater than count of b";
    return 0;
}

出力結果

The string created by using 'aba' 2 times has 5 substring with count of a greater than count of b

この実行例では、文字列 "aba" を 2 回繰り返して作られる "abaaba" の中に、a の個数が b より多い部分文字列が 5 個存在することが確認できます。

計算量について

最悪ケースでは繰り返し回数に比例して走査が必要になるため、時間計算量は O(N × |str|) となります。ただし、途中でカウントが増加しなくなった時点（count2 == 0）や、以降が一定ペースで増えることが確定した時点（count2 == len）で早期に打ち切ることで、実際の計算量を大幅に削減できるのがこのアルゴリズムの利点です。使用するメモリは変数のみのため、空間計算量は O(1) です。