C++で集合{'a','b','c'}のすべての文字を同時に含まない部分文字列の個数を求める方法

文字列 str[] が与えられ、この文字列は 'a'、'b'、'c' の3種類の文字のみで構成されているとします。ここでの目的は、3つの文字すべてを同時に含まない部分文字列の個数を求めることです。

例えば、"a"、"b"、"c"、"abb"、"bba"、"bc"、"ca"、"ccc" といった部分文字列は有効ですが、"abc"、"bcca"、"cab" は 'a'、'b'、'c' のすべてを含んでいるため対象外となります。

具体例で確認してみましょう。

入力: str[] = "aabc"

出力: 集合 {'a', 'b', 'c'} のすべての文字を同時に含まない部分文字列の個数は 8

説明: 対象となる部分文字列は "a", "a", "b", "c", "aa", "ab", "bc", "aab" の8つです。

入力: str[] = "abcabc"

出力: 集合 {'a', 'b', 'c'} のすべての文字を同時に含まない部分文字列の個数は 11

説明: 対象となる部分文字列は "a", "b", "c", "a", "b", "c", "ab", "bc", "ca", "ab", "bc" の11つです。

プログラムで使用するアプローチ

このアプローチでは、長さ n の文字列の部分文字列の総数が n*(n+1)/2 であるという性質を利用します。

まず全体の部分文字列数を初期値として設定し、その後文字列を先頭から走査します。各文字 'a'、'b'、'c' に出会ったタイミングで、残り2文字（'b'と'c'、'c'と'a'、'a'と'b'）の直前の出現位置を確認します。そして、それら2つの位置のうち小さい方の値をカウントから差し引きます。これは、現在の文字を部分文字列に含めたときに3文字すべてが揃ってしまうような部分文字列を除外するためです。

アルゴリズムの手順

• 文字列 str を文字配列として受け取ります。
• 関数 sub_without_all(char str[], int size) は、文字列とその長さを受け取り、'a'、'b'、'c' をすべて同時に含まない部分文字列の個数を返します。
• 初期カウントを size*(size+1)/2 とします。これは str[] の全部分文字列の総数です。
• 変数 a、b、c を用意し、それぞれ str[] 内における 'a'、'b'、'c' の最後の出現位置を記録します。すべて 0 で初期化します。
• for ループを使い、i=0 から i<size まで str[] を走査します。
• str[i] == 'a' の場合は a = i+1 に更新し、count から b と c の小さい方を引きます。
• str[i] == 'b' や str[i] == 'c' の場合も同様に処理します。
• 走査が完了すると、count には3文字すべてを同時に含まない部分文字列の個数が格納されています。
• count を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
    int update_size = size * (size + 1);
    int count = update_size / 2;
    int a, b, c;
    a = b = c = 0;
    for (int i = 0; i < size; i++){
        if (str[i] == 'a'){
            a = i + 1;
            count -= min(b, c);
        }
        else if (str[i] == 'b'){
            b = i + 1;
            count -= min(a, c);
        }
        else{
            c = i + 1;
            count -= min(a, b);
        }
    }
    return count;
}
int main(){
    char str[] = "abcabbc";
    int size = strlen(str);
    cout<<"Count of sub-strings that do not contain all the characters from the set {'a', 'b', 'c'} at the same time are: "<<sub_without_all(str, size);
    return 0;
}

出力

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

Count of sub-strings that do not contain all the characters from the set {'a', 'b', 'c'} at the same time are: 15

このアルゴリズムの計算量は O(n) であり、文字列を一度走査するだけで答えが求まるため、非常に効率的です。全部分文字列を実際に生成して確認する総当たり法（O(n²)〜O(n³)）と比べても、大幅な高速化が実現できます。