C++で各文字が最大k回まで出現する部分文字列を数える方法

文字列 str が与えられたとき、「どの文字も最大 k 回までしか出現しない」ような部分文字列の総数を求めるのがこの問題のゴールです。たとえば、入力が "abc"、k=1 の場合、条件を満たす部分文字列は "a"、"b"、"c"、"ab"、"bc"、"abc" の 6 個になります。

例で理解する

入力 − str="bbddehj", k=1

出力 − 各文字が最大 1 回まで出現する部分文字列の数: 14

説明 − 条件を満たす部分文字列は次のとおりです（同じ文字列でも開始位置が異なれば別々にカウントします）。

"b", "b", "bd", "d", "d", "de", "deh", "dehj", "e", "eh", "ehj", "h", "hj", "j". 合計 14 個.

入力 − str="abc", k=1

出力 − 6

説明 − 部分文字列は次のとおりです。

"a", "b", "c", "ab", "bc", "abc". 合計 6 個.

プログラムで使われているアプローチ

この問題の解き方には、すべての部分文字列を一つずつ検証する素朴な方法（ブルートフォース）と、より効率的な方法があります。以下のコードでは、サイズ 26 の出現回数配列（頻度配列）を活用したシンプルで分かりやすい手法を採用しています。

• 文字列 str とその長さ length を取得します。
• 外側のループで開始位置 i を 0 から length-1 まで動かします。
• i が切り替わるたびに、memset で頻度配列 arr をゼロにリセットします。
• 内側のループで終了位置 j を i から順に伸ばし、文字 str[j] の出現回数を arr[str[j]-'a'] でカウントアップします。
• その文字の出現回数がまだ k 以下であれば、現在の部分文字列 str[i..j] は条件を満たすので count を 1 増やします。
• どこかの文字が k を超えた瞬間に、それ以上長くしても条件を満たせないため、内側のループを break で打ち切ります。ここが無駄な探索を省くポイントです。
• すべての開始位置の処理が終わったら、count を答えとして返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int count_k(string str, int len, int k){
    int count = 0;
    int arr[26];
    for (int i = 0; i < len; i++){
        memset(arr, 0, sizeof(arr));
        for (int j = i; j < len; j++){
            arr[str[j] - 'a']++;
            if (arr[str[j] - 'a'] <= k)
                { count++; }
            else
                { break; }
        }
    }
    return count;
}
int main(){
    string str = "bbddehj";
    int k = 1;
    int length = str.length();
    cout<<"各文字が最大k回まで出現する部分文字列の数: "<<count_k(str, length, k);
    return 0;
}

出力

上記のコードを実行すると、次のような結果が出力されます。

各文字が最大k回まで出現する部分文字列の数: 14

計算量とさらなる高速化

このアルゴリズムの時間計算量は最悪ケースで O(n²)、空間計算量は O(1)（サイズ 26 の固定長配列のみを使用）です。ただし、ある文字の出現回数が k を超えた時点で内側のループを即座に打ち切るため、文字種が多く k が小さい入力では実際の処理量は大きく削減されます。

さらに長い文字列を扱いたい場合は、スライディングウィンドウ（尺取り法）を用いることで O(n) まで高速化できます。右端を伸ばしながら出現回数を更新し、条件を満たさなくなったら左端を進めてウィンドウを修復するという流れで、各右端位置ごとに「有効な部分文字列の個数 ＝ 右端 − 左端 ＋ 1」を加算していきます。