C++で文字列内の最初の一意の文字のインデックスを検索する方法

問題の概要

文字列 s が与えられたとき、その中で繰り返し現れない最初の一意の文字を見つけ、そのインデックスを返すことが課題です。該当する文字が文字列中に存在しない場合は、-1 を返します。

入出力例1

入力:

s = "tutorialspoint"

出力:

1

説明: 文字列「tutorialspoint」の中で、繰り返されない最初の一意の文字は「u」であり、そのインデックスは「1」です。したがって、出力として「1」を返します。

入出力例2

入力:

s = "aaasttarrs"

出力:

-1

説明: 文字列「aaasttarrs」には一意の文字(1回しか現れない文字)が存在しないため、出力として「-1」を返します。

解法のアプローチ:ハッシュマップを活用

与えられた文字列の中で最初に現れる一意の文字のインデックスを効率よく求めるには、ハッシュマップ(unordered_map)を利用するのが効果的です。

基本的な考え方は次のとおりです。まず文字列を先頭から順に走査し、各文字をキー、その出現回数を値とするハッシュマップを作成します。この集計処理には O(n) の線形時間しかかかりません。その後、再度文字列を先頭から走査し、ハッシュマップを参照して出現回数が「1」の文字が見つかった時点で、そのインデックスを返します。

アルゴリズムの手順

1. 文字列 s を入力として受け取ります。
2. 整数を返す関数 uniqueChar(string str) を定義します。この関数は、最初に現れる一意の文字のインデックスを返します。
3. 文字列を走査しながら、文字とその出現回数を対応付けたハッシュマップを作成します。
4. 再度文字列を走査し、出現回数が1の文字が見つかったら、そのインデックスを返します。
5. 一意の文字が1つも存在しない場合は、「-1」を返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int uniqueChar(string str) {
    int ans = -1;
    unordered_map<char, int> mp;

    // 各文字の出現回数をカウント
    for (int i = 0; str[i] != '\0'; i++) {
        mp[str[i]]++;
    }

    // 出現回数が1の最初の文字を探す
    for (int i = 0; i < str.size(); i++) {
        if (mp[str[i]] == 1) {
            ans = i;
            break;
        }
    }
    return ans;
}

int main() {
    string s = "tutorialspoint";
    cout << uniqueChar(s) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

1

説明: 入力文字列「tutorialspoint」には、一意の文字として「u」「r」「l」が含まれています。このうち最初に現れる一意の文字は「u」で、そのインデックスは「1」です。そのため、出力は「1」となります。

計算量について

• 時間計算量: O(n) — 文字列を2回走査するだけなので、文字数 n に対して線形時間で処理できます。
• 空間計算量: O(k) — k は文字列中に現れる異なる文字の種類数です(英小文字のみであれば最大26)。