C++で文字列内の最後の非繰り返し文字を見つける方法

文字列 str が与えられたとき、その中から最後に出現する非繰り返し文字（重複していない文字）を見つける問題を考えてみましょう。例えば、入力文字列が「programming」の場合、後ろから見て最初に一度しか出現しない文字は「n」となります。もし該当する文字が存在しない場合は、-1 を返します。

解決のアプローチ

この問題は、頻度配列（frequency array）を使うことで効率的に解決できます。手順は以下の通りです。

• まず、各文字の出現回数を記録するための頻度配列を作成します。
• 文字列を先頭から走査し、各文字の出現頻度を配列に格納していきます。
• 次に、文字列を末尾から先頭に向かって走査し直します。
• 各文字について、頻度配列の値が 1 であるかどうかを確認します。
• 1 であれば、それが最後の非繰り返し文字なので即座に返します。そうでなければ、前の文字の判定へ進みます。

この方法では、時間計算量は O(n)、空間計算量は O(1)（固定サイズ256の配列を使用）となり、非常に効率的です。

C++での実装例

#include <iostream>
using namespace std;
const int MAX = 256;
static string searchNonrepeatChar(string str) {
    int freq[MAX] = {0};
    int n = str.length();
    // 各文字の出現頻度をカウント
    for (int i = 0; i < n; i++)
        freq[str.at(i)]++;
    // 末尾から走査して最初の非繰り返し文字を探す
    for (int i = n - 1; i >= 0; i--) {
        char ch = str.at(i);
        if (freq[ch] == 1) {
            string res;
            res += ch;
            return res;
        }
    }
    return "-1";
}
int main() {
    string str = "programming";
    cout << "Last non-repeating character: " << searchNonrepeatChar(str);
}

実行結果

Last non-repeating character: n

コードのポイント

• freq[MAX] は ASCII 文字全体（256種類）をカバーできるサイズで宣言しています。
• 1回目のループで各文字の出現回数を集計し、2回目のループで末尾から判定を行うことで、「最後の」非繰り返し文字を正確に特定できます。
• 該当する文字が見つからなかった場合は、文字列 "-1" を返す仕様になっています。