JavaScriptで同じ文字だけを含む部分文字列の数を効率よく数える方法

本記事では、文字列を唯一の引数として受け取り、その中に含まれる「たった1種類の文字だけで構成された連続する部分文字列」の総数を数えるJavaScript関数を作成します。作成した関数は、条件を満たす部分文字列の個数を返します。

問題の概要

例として、入力文字列が次のようになっている場合を考えてみましょう。

const str = 'iiiji';

このとき、期待される出力は次の通りです。

const output = 8;

理由は、条件を満たす部分文字列が以下の8つ存在するためです。

'iii', 'i', 'i', 'i', 'i', 'j', 'ii', 'ii'

解法の考え方

この問題はランレングス（連続する同一文字のかたまり）に着目すると効率的に解けます。長さnの同一文字の連続は、部分文字列を n + (n-1) + ... + 1 = n(n+1)/2 個生み出します。これを利用し、隣接する文字が同じである間だけカウントを加算していくアプローチを採用します。

実装コード

以下が実際のコードです。

const str = 'iiiji';

const countSpecialStrings = (str = '') => {
    let { length } = str;

    // 空文字列の場合は0を返す
    if (!length) {
        return length;
    }

    // 各文字そのものは必ず条件を満たすので、初期値は文字数
    let res = length;

    // j は現在の連続区間の開始位置を指す
    for (let j = 0, i = 1; i < length; ++i) {
        if (str[i] === str[j]) {
            // 同じ文字が続く場合、新たに作られる部分文字列の数を加算
            res += i - j;
        } else {
            // 異なる文字に切り替わったら、区間の開始位置を更新
            j = i;
        }
    }

    return res;
};

console.log(countSpecialStrings(str));

実行結果

コンソールには以下のように出力されます。

8

処理の流れと計算量

このアルゴリズムでは、変数 j が「現在注目している同一文字ブロックの先頭」を保持します。文字 str[i] が str[j] と一致していれば、位置 i を終点とする新しい部分文字列は i - j 個発生します（例えば 'iii' の3文字目では 'ii' と 'iii' の2つ）。異なる文字が出現した時点で j を更新し、次のブロックへ移行します。

• 時間計算量：O(n) — 文字列を一度走査するだけ
• 空間計算量：O(1) — 追加の配列などは不要

全ての部分文字列を列挙して判定する素朴な手法（O(n²)〜O(n³)）と比べ、非常に高速かつメモリ効率の良い解法となっています。