JavaScriptで同じ文字に挟まれた最長部分文字列の長さを求める方法

問題の概要

文字列を引数として受け取るJavaScript関数を作成する必要があります。この関数は、同じ2つの同一文字によって挟まれた部分文字列の中で最も長いものを見つけ、その長さを返します。

入力例と出力例

例えば、以下のような入力文字列を考えてみましょう。

const str = 'sadtrsewak';

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

const output = 6;

なぜなら、2つの「a」の間には長さ6の部分文字列（dtrsew）が存在し、これが条件を満たす最も長い部分文字列だからです。

解決アプローチ

この問題は、各文字が最初に出現した位置を記録しておくことで効率的に解決できます。具体的には、オブジェクト（マップ）を使って各文字の初出インデックスを保存し、同じ文字が再び現れたときに、その間の距離を計算して最大値を更新していきます。

この手法により、文字列を一度走査するだけで答えが求まるため、時間計算量はO(n)となり、非常に効率的です。

実装コード

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

const str = 'sadtrsewak';
const longestSubstringBetween = (str = '') => {
    const map = {};
    let res = -1;
    for(let i = 0; i < str.length; i++){
        const el = str[i];
        if(map.hasOwnProperty(str[i])){
            res = Math.max(res, i - map[el] - 1);
        }else{
            map[el] = i;
        };
    };
    return res;
}
console.log(longestSubstringBetween(str));

コードの解説

処理の流れを順番に見ていきましょう。

1. マップの初期化： オブジェクトmapを用意し、各文字の初出インデックスを記録できるようにします。また、結果を格納する変数resは、該当する部分文字列が存在しない場合に備えて-1で初期化します。

2. 文字列の走査： forループで文字列を先頭から順に走査し、現在の文字を変数elに格納します。

3. 出現チェック： map.hasOwnProperty()を使って、その文字がすでに出現したことがあるかどうかを判定します。

• 出現済みの場合：現在のインデックスiから記録済みの初出インデックスを引き、さらに1を引いた値（挟まれている部分文字列の長さ）を計算し、Math.max()で最大値を更新します。
• 未出現の場合：その文字と現在のインデックスをマップに登録します。

4. 結果の返却： ループ完了後、resを返します。同一文字のペアが存在しなかった場合は-1がそのまま返されます。

実行結果

上記のコードを実行すると、コンソールには以下の出力が表示されます。

6

文字列「sadtrsewak」では、インデックス1と8にある2つの「a」の間に6文字の部分文字列が挟まれているため、正しく6が出力されます。

まとめ

本記事では、ハッシュマップを活用して各文字の初出位置を記録するシンプルかつ効率的なアプローチを紹介しました。線形時間で処理が完結するため、長い文字列に対しても高速に動作します。同様のパターンは、「2つの要素間の最大距離」を求めるさまざまな配列・文字列問題にも応用できるので、ぜひ覚えておきましょう。