JavaScriptで文字列内に最初に重複する文字のインデックスを求める方法

JavaScriptでは、文字列を引数として受け取り、その中で2回目以降に出現する(=重複している)最初の文字のインデックスを返す関数を作成できます。重複する文字がひとつも存在しない場合は、-1 を返す仕様とします。

例として、次のような文字列を考えてみましょう。

const str = 'Hello world, how are you';

この文字列の場合、最初に重複するのは「l」という文字です。「l」はインデックス 2 で初めて出現し、続くインデックス 3 でもう一度現れます。したがって、この関数は 2 を返す必要があります。

アルゴリズムの考え方

この問題を効率よく解くには、Map オブジェクトを使って「すでに登場した文字とそのインデックス」を記録しながら走査する方法が有効です。手順は以下の通りです。

1. 空の Map を用意します。
2. 文字列を先頭から1文字ずつ順番に調べます。
3. 現在の文字が Map にすでに存在していれば、それが最初の重複文字なので、記録しておいたインデックスを即座に返します。
4. 存在しない場合は、現在の文字とそのインデックスを Map に保存し、次の文字へ進みます。
5. 最後まで走査しても重複が見つからなければ、-1 を返します。

コード例

const str = 'Hello world, how are you';

const firstRepeating = str => {
    const map = new Map();
    for(let i = 0; i < str.length; i++){
        if(map.has(str[i])){
            return map.get(str[i]);
        }
        map.set(str[i], i);
    }
    return -1;
};

console.log(firstRepeating(str));

実行結果

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

2

処理の流れの解説

このコードでは、まずインデックス 0 の「H」とインデックス 1 の「e」が初登場のため Map に登録されます。続いてインデックス 2 の「l」も Map に登録されますが、インデックス 3 に進むと再び「l」に遭遇します。この時点で map.has() が true を返すため、保存されていたインデックス 2 が即座に返され、処理は終了します。

計算量について

このアルゴリズムの時間計算量は O(n) です。文字列を一度だけ走査すればよいため、二重ループですべての文字ペアを比較する方法(O(n²))よりも大幅に高速で、長い文字列でも実用的なパフォーマンスを発揮します。また、Map の代わりに Set やプレーンなオブジェクトを使うことも可能ですが、Map を使うと「どの位置の文字が重複したのか」という情報も同時に保持できるため、今回のようなケースに特に適しています。