JavaScriptで文字列内のすべての回文部分列を数える方法【動的計画法】

回文（パリンドローム）とは？

回文（パリンドローム）とは、前から読んでも後ろから読んでも同じになる文字列のことです。例えば、「aba」「madam」「did」などは、いずれも正しい回文の例です。

問題の概要

今回作成するのは、文字列を引数として受け取り、その中に含まれるすべての回文部分列（連続しているかどうかを問わない）の総数を数えて返すJavaScript関数です。

なお、入力として与えられる文字列は「a」「b」「c」「d」の4種類の文字のみで構成されていることが保証されています。

入出力の例

たとえば、入力文字列が次の通りだったとします。

const str = 'bccb';

この場合の出力は次のようになります。

const output = 6;

これは、文字列「bccb」の中には「b」「c」「bb」「cc」「bcb」「bccb」という6つの回文が存在するためです。

実装コード

この問題は動的計画法（DP）を用いることで効率的に解くことができます。以下がその実装例です。

const str = 'bccb';

const countPalindromes = (str = '') => {
    const base = 1000000007;
    const dp = Array.from({ length: str.length }, () => Array(str.length).fill(0));

    for (let l = 1; l <= str.length; l++) {
        for (let i = 0; i + l - 1 < str.length; i++) {
            let j = i + l - 1;

            // 長さ1の部分文字列は常に回文
            if (l === 1) {
                dp[i][j] = 1;
                continue;
            }
            // 長さ2の場合
            if (l === 2) {
                dp[i][j] = 2;
                continue;
            }

            if (str[i] === str[j]) {
                let left = i + 1, right = j - 1;
                while (left <= right && str[left] != str[i]) left++;
                while (left <= right && str[right] != str[i]) right--;

                if (left > right) {
                    // 内側に同じ文字が存在しない場合
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                } else if (left === right) {
                    // 内側に同じ文字が1つだけ存在する場合
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                } else {
                    // 内側に同じ文字が複数ある場合は重複分を差し引く
                    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
                }
            } else {
                // 両端が異なる場合は包除原理で計算
                dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
            }

            // オーバーフロー防止のための剰余演算
            dp[i][j] = dp[i][j] < 0 ? dp[i][j] + base : dp[i][j] % base;
        }
    }
    return dp[0][str.length - 1];
};

console.log(countPalindromes(str));

アルゴリズムのポイント

• dp[i][j]：部分文字列 str[i...j] に含まれる回文部分列の個数を格納します。
• 長さ1の場合：単一の文字は常に回文となるため、個数は1になります。
• 長さ2の場合：それぞれの文字単体の2つを数えます。
• 両端の文字が一致する場合：内側に同じ文字がいくつ存在するかに応じて、新しく作られる回文の数を加算したり、重複分を減算したりして求めます。
• 両端の文字が異なる場合：包除原理を利用し、dp[i][j-1] ＋ dp[i+1][j] − dp[i+1][j-1] として計算します。
• 剰余演算：値が巨大化するのを防ぐため、10⁹ ＋ 7 で割った余りを常に保持します。

出力結果

コンソールに出力される結果は次の通りです。

6