【C++】指定された文字列の部分文字列内の最後の非反復文字を求めるクエリの解き方

この記事では、与えられた文字列 str と Q 個のクエリ(各クエリは2つの整数で構成)に対して、C++ で「指定された文字列の部分文字列内にある、一度しか登場しない文字のうち最も右側にあるもの(最後の非反復文字)」を検索するプログラムを作成します。文字列処理とクエリ処理の定番テクニックである累積カウント(プリフィックスカウント)を活用した効率的な解法をわかりやすく解説します。

問題の説明

各クエリには2つの整数 L と R が与えられます。クエリを処理する際は、インデックス L から R までの部分文字列を取り出し、その中で繰り返し現れない(出現回数が1回だけの)最後の文字を見つけます。該当する文字が存在しない場合は -1 を返します。

具体例で確認しましょう。

入力:str = "Tutorialspoint"、Q = 2
query = {{4, 8}, {2, 6}}

出力:s、a

解説

subStr[4…8] = "rials"。r・i・a・l・s はいずれも1回しか登場しないため、後ろから調べると最初にヒットする非反復文字は s です。

subStr[2…6] = "toria"。こちらも全文字が1回ずつ登場するため、答えは a です。

逆に、部分文字列が "abcabc" のようにすべての文字が2回以上現れる場合は非反復文字が存在しないため、-1 を返します。

解法アプローチ

各クエリで部分文字列を毎回走査して出現回数を数える素朴な方法でも正解は得られますが、クエリ数や文字列長が大きくなると計算コストが課題になります。そこで、あらかじめ各位置までの文字出現数を累積的に記録しておく前計算を行います。

1. 2次元配列 charFreq[256][N] を用意し、charFreq[c][i] に「インデックス 0〜i の範囲における文字 c の出現回数」を格納します。
2. 任意の区間 [L, R] 内での文字 c の出現回数は、charFreq[c][R] − charFreq[c][L−1] で O(1) に求められます。
3. クエリ処理では、インデックス R から L へ向かって順に文字を確認し、区間内の出現回数がちょうど1になる最初の文字を答えとして返します。見つからなければ "-1" を返します。

これにより、前計算を O(256 × N) で行えば、以降の各クエリには区間長に比例した時間で回答できるため、多数のクエリが発生するケースにも効率的に対応できます。

C++ 実装例

#include<bits/stdc++.h>
using namespace std;
int charFreq[256][1000] = {0};
void initialiseCharFrequency(string str, int n) {
    charFreq[(int)str[0]][0] = 1;
    for (int i = 1; i < n; i++) {
        char ch = str[i];
        for (int j = 0; j < 256; j++) {
            char charToUpdate = (char)j;
            if (charToUpdate == ch)
                charFreq[j][i] = charFreq[j][i - 1] + 1;
            else
                charFreq[j][i] = charFreq[j][i - 1];
        }
    }
}
string returnCharFromString(char x) {
    string s(1, x);
    return s;
}
string lastUniqueChar(string str, int n, int start, int end) {
    for (int i = end; i >= start; i--) {
        char ch = str[i];
        if ((charFreq[(int)ch][end] - charFreq[(int)ch][start - 1]) == 1)
            return returnCharFromString(ch);
    }
    return "-1";
}
int main() {
    string str = "TutorialsPoint";
    int len = str.length();
    int Q = 3;
    int query[Q][2] = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
    initialiseCharFrequency(str, len);
    for (int i = 0; i < Q; i++)
        cout<<"\nFor Query "<<(i+1)<<": The last non-repeating character in the sub-string of a given string is "<<lastUniqueChar(str, len, query[i][0], query[i][1]);
}

出力

For Query 1: The last non-repeating character in the sub-string of a given string is P
For Query 2: The last non-repeating character in the sub-string of a given string is o
For Query 3: The last non-repeating character in the sub-string of a given string is n

実行結果は以下のように解釈できます。

• クエリ1(インデックス 2〜9、部分文字列 "torialsP"):t と o は2回登場しますが、それ以外は1回のみ。後ろから見て最初の非反復文字は P です。
• クエリ2(インデックス 2〜3、部分文字列 "to"):t も o も1回ずつなので、答えは o です。
• クエリ3(インデックス 0〜12、部分文字列 "TutorialsPoin"):t・o・i は2回登場しますが、後ろ側の n は1回だけなので答えは n です。

計算量の目安

• 前計算:O(256 × N)(N は文字列長)
• クエリ1件あたり:最大 O(N)(区間長に比例)
• 空間計算量:O(256 × N)

なお、本実装では簡潔さを優先して固定サイズの配列を使用していますが、実際の運用では vector を使って文字列長に応じて動的にメモリを確保すると、より安全で柔軟な実装になります。