【Java】 ~アルゴリズム徹底解説~ 文字列から繰り返されない最初の文字を抽出する良い方法・悪い方法

対象読者

• アルゴリズムの学習中の人
• HashMapなどのデータ構造を使いこなせるようになりたい人
• Javaでアルゴリズム問題に挑戦している人

---

問題の前提条件

• 文字列の各要素は英小文字などの単一文字（char）とする。
• すべての文字が重複している場合は -1 を返す。

---

問題

文字列の中から、最初に繰り返しがない文字のインデックスを返す関数を作成せよ。

例：
s = "arunbababa" の場合
"r" が最初に一度だけ出現する文字なので、インデックス1 を返す。

---

解き方パターン1：Brute Force（よくない例）

// 文字列の中から繰り返しがない文字のインデックスを返す（非効率な例）
// pre: s = "arunbababa"
// post: 1（rが該当の文字でインデックスは1）
public int firstUniqChar(String s) {
    // 要素数が1以下なら比較する必要がないため0を返す
    if (s.length() <= 1) return 0;

    // 文字列sを配列に変換
    char[] chars = s.toCharArray();

    // 出現回数を保持するためのハッシュマップを作成
    Map<Character, Integer> map = new HashMap<>();

    // 文字列の各文字を二重ループで比較する
    for (char c1 : chars) {
        for (char c2 : chars) {
            // ハッシュマップにキー（文字）が登録されていなければ初期化
            if (!map.containsKey(c2)) {
                map.put(c2, 1);
            }
            // すでに登録されている場合は、そのキーのバリューを +1 する
            else {
                map.put(c2, map.get(c2) + 1);
            }
        }
    }

    // ハッシュマップを使って出現回数が1の文字を探す
    for (int i = 0; i < chars.length; i++) {
        if (map.get(chars[i]) == 1) {
            return i;
        }
    }

    // 一度しか現れない文字が存在しない場合は -1 を返す
    return -1;
}

---

何がいけないのか

この実装では、外側のループ（i）ごとに内側のループ（j）を全走査しており、
文字列長を n としたときに、計算量は O(n²) となる。

つまり、文字数が増えるほど比較回数が 指数的に増加 する構造になっている。

さらに、

• 各ループで毎回 map にアクセスしているため無駄が多い
• 一度カウントした文字も何度も再計算している
  という点でも非効率。

このような処理は、小規模データでは動作するものの、
データ量が増えるとパフォーマンスが大幅に低下する。

次のパターンでは、これを効率化してO(n)で処理する方法を紹介する。

---

解き方パターン2：HashMapを使った最適化例

// 文字列の中から繰り返しがない文字のインデックスを返す
// pre: s = "arunbababa"
// post: 1 (rが該当の文字で、インデックスは1)
public int firstUniqChar(String s) {
    // 文字列の長さが1なら、唯一の文字が一意なので0を返す
    if (s.length() == 1) return 0;

    // 各文字の出現回数を記録するためのハッシュマップを用意
    Map<Character, Integer> map = new HashMap<>();
    
    // 文字列sを左から右へ走査し、各文字の出現回数をカウントする
    for (char c : s.toCharArray()) {
        // まだ登録されていない文字ならカウント1で登録
        if (!map.containsKey(c)) {
            map.put(c, 1);
        }
        // すでに登録済みの文字ならカウントを+1する
        else {
            map.put(c, map.get(c) + 1);
        }
    }
    
    // もう一度文字列を左から右に走査し、
    // 出現回数が1回の文字のインデックスを返す
    int index = 0;
    for (char c : s.toCharArray()) {
        if (map.get(c) == 1) {
            return index;
        }
        index++;
    }

    // 1回しか現れない文字が存在しない場合は-1を返す
    return -1;
}

何がいいか

• 配列を1回のリニアスキャンの中でハッシュマップの検査もすることで、計算量をO(n)に抑えられている(ネストされたループを避けられている)

補足

いい例のほうはループ処理が2回ありますが、どちらもn回のループなので全体として2nのループとなります。
計算量としては係数は無視できるのでO(n)となります。

---

比較とポイント

観点	悪い例（Brute Force）	良い例（最適化）
計算量	O(n²)	O(n)
ループ構造	ネストされた二重ループ	単一ループ×2回
データ構造の使い方	非効率に何度も再登録	HashMapを一度構築
パフォーマンス	入力サイズに比例して急激に悪化	線形に伸びるのみ

---

まとめ

• ネストされたループ構造は、要素数が増えると急激に処理時間が増加するので避けましょう。
• HashMapを用いれば、一度の走査でカウントを記録し、次の走査で結果を抽出できます。
  • このループとハッシュマップの組み合わせで配列に対するチェック系問題は最適に解ける問題が多いのでしっかりとマスターしましょう。
• 「記録しつつ検索」は、重複検出・出現回数問題の基本となりますので、パターン化して理解しましょう。

---