ค้นหาตัวอักษรที่ไม่ซ้ำตัวสุดท้ายในซับสตริงใน C++

ภาพรวมปัญหา

ได้รับสตริง str และ Q คำถาม แต่ละคำถามมีช่วง [L, R] หาตัวอักษรที่ไม่ซ้ำ (non-repeating) ตัวสุดท้ายในซับสตริง str[L..R]

ตัวอย่าง

Input: str = "Tutorialspoint", Q = 2
Query 1: [4, 8] -> substring "rials" -> last non-repeating = 's'
Query 2: [2, 6] -> substring "toria" -> last non-repeating = 'a'

แนวทางแก้ปัญหา

• สร้างตารางความถี่สะสม charFreq[256][n] สำหรับแต่ละตัวอักษร
• สำหรับแต่ละคำถาม ตรวจสอบจากขวาไปซ้าย หาตัวอักษรที่มีความถี่ในช่วง = 1

ตัวอย่างโค้ด 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++) {
            if ((char)j == ch)
                charFreq[j][i] = charFreq[j][i-1] + 1;
            else
                charFreq[j][i] = charFreq[j][i-1];
        }
    }
}

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 string(1, ch);
    }
    return "-1";
}

int main() {
    string str = "TutorialsPoint";
    int len = str.length();
    initialiseCharFrequency(str, len);
    // ... process queries
    return 0;
}