【JavaScript】文字列内で連続して繰り返される文字の最大数を取得する方法

問題の概要

以下のように、同じ文字が繰り返し含まれる文字列があるとします。

const a = "fdsfjngjkdsfhhhhhhhhhhhfsdfsd";

私たちの課題は、同じ文字が連続して出現する最大回数（ストリークの長さ）を返す関数を実装することです。上記の文字列では、文字「h」が11回連続して出現しているため、この文字列を渡した場合の関数の戻り値は11となります。

アプローチ：スライディングウィンドウアルゴリズム

この種の問題は、スライディングウィンドウ（滑動窓）アルゴリズムが非常に有効です。ここでいう「安定したウィンドウ」とは、同じ文字のみが連続して含まれている区間のことを指し、異なる文字が混在する区間は「不安定」な状態とみなします。

ウィンドウは、末尾に新しい文字を追加しながら広げていき、異なる文字が出現した時点で先頭をリセットする、という動きを繰り返します。これにより、文字列を一度の走査だけで連続文字の最大長を求めることができます。

実装例

スライディングウィンドウアルゴリズムを使用した関数のコードは以下の通りです。

const a = "fdsfjngjkdsfhhhhhhhhhhhfsdfsd";
const findMaximumRepeating = str => {
    let max = 0;
    for(let start = 0, end = 1; end < str.length; ){
        if(str[end] === str[start]){
            if(max < end - start + 1){
                max = end - start + 1;
            };
            end++;
        } else {
            start = end;
        };
    };
    return max;
};
console.log(findMaximumRepeating(a));

出力結果

コンソールへの出力は以下のようになります。

11

コードの解説

この実装では、ウィンドウの先頭を示す start と末尾を示す end の2つのポインターを使用しています。

• str[end] が str[start] と同じ文字の場合：ウィンドウを拡張（end++）し、現在の連続長（end - start + 1）がこれまでの最大値を上回っていれば更新します。
• 異なる文字が出現した場合：start を end の位置へ移動し、新しい連続区間の計測をやり直します。

文字列を一度だけ走査するため、計算量は O(n) と非常に効率的です。文字列の長さが大きくなっても高速に動作するのが、このアルゴリズムの大きなメリットです。