JavaScriptで文字列から構築できる最長回文の長さを求める方法

問題の概要

小文字または大文字のアルファベットのみで構成された文字列 s が与えられたとき、これらの文字を使って構築できる最も長い回文の長さを返す必要があります。なお、大文字と小文字は区別されるため、たとえば「Aa」は回文として扱われません。

例

入力文字列が次の場合を考えてみましょう。

const str = "abccccdd";

このとき出力は 7 になります。これは、「dccaccd」という長さ7の回文をこれらの文字で構築できるためです。

解決のアプローチ

回文を構築するには、同じ文字がペア(2つ)で必要です。そこで、各文字の出現状況を追跡し、ペアが成立するたびに長さを2ずつ加算していきます。さらに、奇数個残った文字が1つでも存在すれば、それを回文の中央に配置できるため、最終的な長さに1を追加します。

ここでは JavaScript の Set オブジェクトを活用し、以下の手順で処理を行います。

• 文字列を先頭から順に走査する。
• その文字がすでにセット内に存在すれば、ペアが見つかったことを意味するため、カウントを2増やしてセットから削除する。
• 存在しなければ、その文字をセットに追加する。

走査完了後、セットに残っている文字は奇数回出現した文字です。1つでも残っていれば、それを回文の中心に置けるので、答えに1を足します。

コード例

const str = "abccccdd";
const longestPalindrome = (str) => {
    const set = new Set();
    let count = 0;
    for (const char of str) {
        if (set.has(char)) {
            count += 2; set.delete(char);
        }
        else {
            set.add(char);
        }
    }
    return count + (set.size > 0 ? 1 : 0);
};
console.log(longestPalindrome(str));

実行結果

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

7

計算量の目安

このアルゴリズムの時間計算量は O(n)(n は文字列の長さ)、空間計算量は O(k)(k は異なる文字の種類数、英字のみなら最大52種類)となり、非常に効率的です。