JavaScriptで解く！『LeetCode Arai 60』#4 First Unique Character in a String

この記事では、LeetCode Arai 60 シリーズ第4問、First Unique Character in a String を JavaScript を使って解く方法を解説します。

---

問題の概要

文字列 s が与えられます。この中から、

1. 一度しか登場しない文字
2. その中で、一番最初に現れる文字の位置（インデックス）

を見つける問題です。

もしそのような文字が存在しなければ -1 を返します。

---

例

入力例1

s = "loveleetcode"

• "l" → 1回だけ登場（インデックス 0）
• "o" → 2回登場
• "v" → 1回だけ登場（インデックス 2）
• "e" → 4回登場
  ...

最初に一度しか登場しない文字は "l" → インデックス 0 を返す。

入力例2

s = "aabb"

• 全ての文字が複数回登場 → 答えは -1

---

アプローチ

この問題では、「最初に一度しか登場しない文字」を見つけるために、次の方法を取ります。

1. 各文字の登場回数 を記録するためにハッシュマップ（{}）を使用します。
2. 文字の登場順 を保持するために、別途 配列 を活用します。
   • ハッシュマップだけだと順序が保証されないため、配列で順序を管理します。
3. 2つのループで処理します。
   • 1回目のループ: 各文字の登場回数を記録。
   • 2回目のループ: 順序を保持した配列を走査し、最初に登場回数が1の文字を探します。

---

コード

以下が、このアプローチを実装したコードです。

var firstUniqChar = function(s) {
    const charCount = {}; // 各文字の登場回数を記録
    const charOrder = []; // 各文字の登場順を記録

    // 1. 登場回数と順序を記録
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (!charCount[char]) {
            charCount[char] = 1;
            charOrder.push(char); // 新しい文字なら順序も記録
        } else {
            charCount[char]++;
        }
    }

    // 2. 順序に従い、登場回数が1の文字を探す
    for (const char of charOrder) {
        if (charCount[char] === 1) {
            return s.indexOf(char); // 最初に登場した位置を返す
        }
    }

    // 3. 該当する文字がない場合は -1 を返す
    return -1;
};

---

コード解説

ステップ1: 登場回数と順序を記録

• ハッシュマップ（charCount）を使って、各文字が何回登場したか記録します。
• 同時に、登場順を保持するために配列（charOrder）に文字を追加します。

サンプル実行（s = "loveleetcode"）

charCount = { l: 1, o: 2, v: 1, e: 4, t: 1, c: 1, d: 1 };
charOrder = ["l", "o", "v", "e", "t", "c", "d"];

---

ステップ2: 順序に従い、登場回数をチェック

• 配列 charOrder を順に走査し、登場回数が 1 の文字を見つけます。
• その文字のインデックスを s.indexOf(char) で返します。

サンプル実行（charOrder = ["l", "o", "v", "e", "t", "c", "d"]）

1. "l" → 登場回数 1 → s.indexOf("l") = 0 を返す
2. もし見つからなければ次の文字をチェックします。

---

ステップ3: 見つからなければ -1 を返す

• 配列を最後まで見ても「登場回数1の文字」が見つからなければ、-1 を返します。
• これは「一度しか登場しない文字がない」場合を意味します。

---

なぜ配列を使うか？

• 順序保証の問題を解決
  ハッシュマップ（charCount）は順序が保証されませんが、配列（charOrder）を併用することで、文字列内での順序を正確に保持できます。

• 効率的な処理

  • 1回目のループ: O(n) （文字列を走査）
  • 2回目のループ: O(k) （文字数に比例、最大でも n）
    合計 O(n) 時間で処理が可能です。

---

動作例

入力例1: s = "loveleetcode"

1. 1回目のループ結果

   charCount = { l: 1, o: 2, v: 1, e: 4, t: 1, c: 1, d: 1 };
   charOrder = ["l", "o", "v", "e", "t", "c", "d"];
   

2. 2回目のループ処理

   • "l" → 登場回数 1 → s.indexOf("l") = 0
     結果: 0

---

入力例2: s = "aabb"

1. 1回目のループ結果

   charCount = { a: 2, b: 2 };
   charOrder = ["a", "b"];
   

2. 2回目のループ処理

   • "a" → 登場回数 2
   • "b" → 登場回数 2
     結果: -1

---

まとめ

• First Unique Character in a String は、「一度しか登場しない文字」を見つける問題です。
• 配列を併用することで、順序の問題を解決し、正確な処理が可能です。
• このアプローチは、時間計算量 O(n)、空間計算量 O(n) で効率的に解決できます。

配列とハッシュマップを組み合わせる方法は、文字列操作の問題を解くうえで非常に有効です。

他の類似問題でも応用してみてください！