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

本記事では、文字列を引数として受け取り、同じ文字2つに挟まれた最長の部分文字列の長さを求めて返すJavaScript関数の実装方法を解説します。

問題の概要

与えられた文字列の中から、「同じ文字で始まり、同じ文字で終わる」部分文字列を探し、その間にある文字数（挟まれた部分の長さ）が最大になるものを見つけます。

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

const str = 'avbghvh';

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

const output = 3;

理由は簡単で、2つの「v」の間に挟まれた部分文字列 'bgh' の長さが 3 であり、これが条件を満たす最長の部分文字列だからです。

解決アプローチ

この問題は、Map（ハッシュマップ）を使うことで効率的に解決できます。基本的な考え方は以下のとおりです。

• 各文字が最初に出現したインデックスをMapに記録します。
• ループ処理の中で同じ文字が再び出現した場合、現在のインデックスと最初の出現位置の差分から挟まれた文字数を計算します。
• 計算結果がこれまでの最大値より大きければ、最大値を更新します。

この方法なら、文字列を一度走査するだけで答えが求まるため、時間計算量 O(n) の非常に効率的なアルゴリズムになります。

実装コード

const str = 'avbghvh';

const longestSub = (str = '') => {
    const map = new Map();
    let max = -1;
    for(let i = 0; i < str.length; i++){
        if(map.has(str.charAt(i))){
            max = Math.max(max, i - map.get(str.charAt(i)) - 1);
        }else{
            map.set(str.charAt(i), i);
        };
    };
    return max;
};

console.log(longestSub(str));

コードのポイント

• map: 各文字の最初の出現インデックスを保存するためのMapオブジェクトです。
• max: 見つかった最長の長さを保持する変数です。該当する部分文字列が存在しない場合に備え、初期値は -1 に設定しています。
• i - map.get(...) - 1: 同じ文字同士のインデックス差から1を引くことで、両端の文字自体を除いた「挟まれた部分」の正確な長さを求めています。

実行結果

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

3

これは、文字列 'avbghvh' 内の2つの「v」に挟まれた部分文字列 'bgh' の長さが 3 であることを示しています。

まとめ

同じ文字に挟まれた最長部分文字列の長さを求める問題は、Mapで各文字の初出位置を管理するシンプルな手法で線形時間（O(n)）で解くことができます。類似の「文字の出現位置を記録しながら走査する」パターンは、他の文字列操作の問題にも応用できるため、ぜひ覚えておきましょう。