C++でちょうどk種類の異なる文字を含む部分文字列の個数を数える方法

小文字の英字のみで構成される文字列 str と整数値 k が与えられたとき、文字列 str の部分文字列のうち「ちょうど k 種類の異なる文字」を含むものの個数を求めるのが本記事の目的です。

入力例と出力例

例1

入力:

str= "pqr" k=2

出力:

ちょうど2種類の異なる文字を含む部分文字列の個数: 2

説明:

ちょうど2種類の異なる文字を含む部分文字列は「pq」と「qr」の2つです。

例2

入力:

str= "stristr" k=4

出力:

ちょうど4種類の異なる文字を含む部分文字列の個数: 10

説明:

該当する部分文字列は以下の10個です。
「stri」「tris」「rist」「istr」「stris」「trist」「ristr」「strist」「tristr」「stristr」

アルゴリズムの考え方

このアプローチでは、26個の要素を持つ配列 array[26] を用いて、文字列 str 内に含まれる各英字の出現頻度を管理します。そのうえで、二重の for ループによって文字列を走査し、部分文字列内で各文字が初めて出現するたびに一意な文字数をカウントアップします。そして、各部分文字列の走査が終わった時点でこのカウントが k と一致していれば、条件を満たす部分文字列の総数を1つ増やします。

• 文字列 str を入力として受け取ります。
• 正の整数 k を入力として受け取ります。
• 関数 substring_k(string str, int length, int k) は、str と k を引数に取り、ちょうど k 種類の異なる文字を含む部分文字列の個数を返します。
• カウント用変数 count を 0 で初期化します。
• 出現頻度を記録するための配列 array[26] を用意します。
• i = 0 ～ length - 1、j = i ～ length - 1 の範囲で二重ループにより文字列を走査します。
• 変数 temp には、部分文字列 str[i..j] 内に含まれる一意な文字の数を格納します。
• array[str[j] - 'a'] == 0 のとき、文字 str[j] はこの部分文字列内で初めて登場したことを意味するため、temp をインクリメントします。
• 続いて array[str[j] - 'a']++ により、現在の文字の出現回数を更新します。
• temp が k と等しければ、count をインクリメントします。
• temp が k を超えた場合は、それ以上計算を続けても無駄なので break でループを抜けます。
• すべてのループが完了したら、count を結果として返します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int substring_k(string str, int length, int k){
    int count = 0;
    int array[26];
    for (int i = 0; i < length; i++){
        int temp = 0;
        memset(array, 0, sizeof(array));
        for (int j = i; j < length; j++){
            if(array[str[j] - 'a'] == 0){
                temp++;
            }
            array[str[j] - 'a']++;
            if (temp == k){
                count++;
            }
            if(temp > k){
                break;
            }
        }
    }
    return count;
}
int main(){
    string str = "abc";
    int length = str.length();
    int k = 1;
    cout<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
    return 0;
}

実行結果

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

Count of number of substrings with exactly k distinct characters are: 3