【C++】文字のASCII値の合計がkで割り切れる「長さkの部分文字列」の個数を効率的に求める方法

問題の概要

本記事では、文字列と整数 k が与えられたときに、「長さがちょうど k である部分文字列のうち、構成する各文字のASCII値の合計が k で割り切れるもの」の個数を求めるアルゴリズムを解説します。

例として、文字列が "BCGABC"、k = 3 の場合を考えてみましょう。部分文字列 BCG のASCII値の合計は 204（B=66、C=67、G=71）であり、また ABC の合計は 198（A=65、B=66、C=67）です。これらはいずれも k = 3 で割り切れるため、答えは 2 となります。

アプローチ：スライディングウィンドウ法

この問題は、スライディングウィンドウ（sliding window）と呼ばれる手法を用いることで効率的に解けます。手順は以下の通りです。

1. 最初の長さ k の部分文字列に含まれる文字のASCII値の合計を求めます。
2. その合計が k で割り切れる場合は、カウントを1増やします。
3. ウィンドウを1文字分右へずらす際には、ウィンドウの左端から外れる文字のASCII値を合計から引き算し、新しく右端に入ってくる文字のASCII値を足し算します。
4. スライドのたびに合計が k で割り切れるかどうかを判定し、割り切れればカウントを増やします。

各ステップで合計をゼロから再計算する必要がないため、文字列の長さを n としたとき全体の計算量は O(n) に抑えられます。

C++による実装例

#include <iostream>
using namespace std;

int countKLenSubstr(string str, int k) {
    int len = str.length();
    int sum = 0;
    int count = 0;

    // 最初の長さkの部分文字列のASCII値の合計を求める
    for (int i = 0; i < k; i++)
        sum += str[i];

    if (sum % k == 0)
        count++;

    // ウィンドウをスライドしながら判定
    for (int i = k; i < len; i++) {
        int prev_ascii = str[i - k]; // ウィンドウの左端の文字のASCII値
        sum -= prev_ascii;           // 左端の文字を除外
        sum += str[i];               // 新しく入る文字のASCII値を加算

        if (sum % k == 0)
            count += 1;
    }
    return count;
}

int main() {
    string s = "BCGABC";
    int k = 3;
    cout << "Number of substrings: " << countKLenSubstr(s, k);
}

実行結果

Number of substrings: 2

処理の流れの確認

上記のコードでは、次のような流れで処理が進みます。

• BCG：合計 204 → 3で割り切れる ✔
• CGA：合計 203 → 割り切れない ✘
• GAB：合計 202 → 割り切れない ✘
• ABC：合計 198 → 3で割り切れる ✔

そのため、条件を満たす部分文字列は BCG と ABC の2つとなり、出力は 2 になります。

まとめ

部分文字列の合計を毎回一から計算する素朴な方法では計算量が O(n×k) になりますが、スライディングウィンドウ法を使えば「1文字除いて1文字足す」という更新だけで済むため、O(n) まで高速化できます。文字列処理において累積和やウィンドウ操作は頻出のテクニックなので、ぜひ覚えておきましょう。