Truy vấn ký tự không lặp cuối cùng trong xâu con C++

Cho chuỗi str và Q truy vấn. Mỗi truy vấn cho L, R (0-based). Tìm ký tự cuối cùng trong xâu con str[L..R] chỉ xuất hiện 1 lần trong xâu con đó.

Ví dụ

str = "TutorialsPoint"
Query 1: L=2, R=9 → xâu con "torialsP" → ký tự cuối không lặp: 'P'
Query 2: L=2, R=3 → "to" → 'o'
Query 3: L=0, R=12 → toàn bộ → 'n'

Thuật toán tiền xử lý tần suất tiền tố

Xây dựng mảng freq[256][len]: freq[c][i] = số lần ký tự c xuất hiện trong str[0..i].

Tần suất trong [L, R]: freq[c][R] - (L>0 ? freq[c][L-1] : 0).

Với mỗi truy vấn, duyệt từ R về L, tìm ký tự đầu tiên có tần suất = 1.

Chương trình C++

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

const int MAXLEN = 1000;
int freq[256][MAXLEN];

void buildFreq(const string& s) {
    int n = s.size();
    for (int c = 0; c < 256; c++) freq[c][0] = 0;
    freq[(int)s[0]][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int c = 0; c < 256; c++)
            freq[c][i] = freq[c][i-1];
        freq[(int)s[i]][i]++;
    }
}

char queryLastUnique(const string& s, int L, int R) {
    for (int i = R; i >= L; i--) {
        char c = s[i];
        int cnt = freq[(int)c][R] - (L > 0 ? freq[(int)c][L-1] : 0);
        if (cnt == 1) return c;
    }
    return '-1'; // Không tìm thấy
}

int main() {
    string str = "TutorialsPoint";
    buildFreq(str);
    int Q = 3;
    int queries[3][2] = {{2,9}, {2,3}, {0,12}};
    for (int i = 0; i < Q; i++) {
        char ans = queryLastUnique(str, queries[i][0], queries[i][1]);
        cout << "Query " << i+1 << ": " << ans << endl;
    }
    return 0;
}

Kết quả

Query 1: P
Query 2: o
Query 3: n

Độ phức tạp

• Tiền xử lý: O(256 × N)
• Mỗi truy vấn: O(R-L+1) ≤ O(N)
• Có thể tối ưu truy vấn O(1) với cấu trúc dữ liệu phức tạp hơn (segment tree + bitset).