JavaScriptで文字列から構築できる回文（パリンドローム）の数を数える方法

本記事では、文字列と数値を引数として受け取り、その文字列に含まれる文字を使って構築できる「指定した長さの回文」の総数を求めるJavaScript関数の実装方法を解説します。

問題の概要

第一引数に文字列(str)、第二引数に数値(num)を受け取るJavaScript関数を作成します。この関数は、与えられた文字列strの文字を組み合わせて、ちょうどnum文字となる回文が何通り作れるかを数え、その個数を返す必要があります。

たとえば、入力が以下の場合を考えてみましょう。

const str = 'ij';
const num = 4;

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

const output = 4;

これは、次の4つの回文が構築できるためです。

'iiii', 'jjjj', 'ijji', 'jiij'

アプローチ

まず、ハッシュセット(Set)を使って、与えられた文字列に含まれる一意な文字の種類数を数えます。この種類数をuとします。

回文の長さ(num)が奇数の場合、中央の文字は左右対称の制約を受けないため、u通りの候補から自由に選ぶことができます。

一方、numが偶数の場合、作れる回文の総数は次の式で表されます。

power(u, num / 2)

さらにnumが奇数の場合は、中央の位置の選択肢としてu通りが加わるため、この値にuを掛け合わせればよいことになります。

コード例

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

const str = 'ij';
const num = 4;

const findValidPalindromes = (str = '', num = 1) => {
    const set = new Set();
    for (let i = 0; i < str.length; i++) {
        const el = str[i];
        set.add(el);
    }
    const u = set.size;
    if (num & 1) {
        return Math.pow(u, num / 2) * u;
    } else {
        return Math.pow(u, num / 2);
    }
};

console.log(findValidPalindromes(str, num));

出力結果

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

4