JavaScriptで文字列内の最初の「重複しない文字」のインデックスを検索する方法

問題の概要

今回は、文字列を唯一の引数として受け取る JavaScript関数を作成します。この関数が満たすべき要件は以下の通りです。

• 文字列の中で一度だけ出現する最初の文字を見つけ、そのインデックスを返す
• 一意な文字（重複していない文字）がひとつも存在しない場合は -1 を返す

入力例

const str = 'hellohe';

この文字列の場合、「o」が最初に登場する位置はインデックス4なので、期待される出力は次のようになります。

const output = 4;

解決のアプローチ

この問題は、以下の手順で効率よく解くことができます。

• 1回目の走査：各文字について「出現回数」と「最初に出現したインデックス」をハッシュマップ（オブジェクト）に記録する
• 2回目の走査：記録した情報をもとに、出現回数が1回の文字を探し、そのインデックスを返す

この方法なら、計算量は O(n) となり、長い文字列でも高速に処理できます。

実装例

上記のアプローチを実装したコードがこちらです。

const str = 'hellohe';

const firstUnique = (str = '') => {
    let obj = {};
    // 1回目の走査：出現回数と最初のインデックスを記録
    for(let i = 0; i < str.length; i++){
       if(str[i] in obj){
           let temp = obj[str[i]];
           let x = parseInt(temp[0]);
           x += 1;
           temp[0] = x;
           obj[str[i]] = temp;
       } else {
           obj[str[i]] = [1, i]; // [出現回数, インデックス]
       }
    }
    // 2回目の走査：出現回数が1の文字を探す
    let arr = Object.keys(obj);
    for(let i = 0; i < arr.length; i++){
       let z = obj[arr[i]];
       if(z[0] === 1){
           return z[1];
       }
    }
    return -1; // 一意な文字が存在しない場合
};

console.log(firstUnique(str));

実行結果

4

より簡潔な別解：Mapを使った書き方

ES6で導入された Map を使うと、コードをより読みやすく書き直せます。

const firstUniqueSimple = (str = '') => {
    const counts = new Map();
    
    for (const ch of str) {
       counts.set(ch, (counts.get(ch) || 0) + 1);
    }
    
    for (let i = 0; i < str.length; i++) {
       if (counts.get(str[i]) === 1) return i;
    }
    
    return -1;
};

console.log(firstUniqueSimple('hellohe')); // 4

まとめ

文字列内で最初に一度だけ登場する文字を探すには、ハッシュマップで出現回数を記録し、再度走査して確認するのが定石です。計算量 O(n)・メモリ量 O(k)（kは文字の種類数）で動作するため、実務でも十分なパフォーマンスが得られます。一意な文字が見つからないケースへの対応として -1 を返す点も忘れずに実装しましょう。