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

สมมติว่ามีสตริง str เราต้องหาตัวอักษรที่ไม่ซ้ำตัวสุดท้ายในมัน ดังนั้นถ้าสตริงอินพุตเป็น "programming" ตัวอักษรที่ไม่ซ้ำตัวแรกคือ 'n' หากไม่มีตัวอักษรดังกล่าว ให้คืนค่า -1

เราสามารถแก้ได้โดยการสร้างอาร์เรย์ความถี่ (Frequency Array) ซึ่งจะเก็บความถี่ของแต่ละตัวอักษรของสตริงที่กำหนด เมื่อความถี่ถูกอัปเดตแล้ว ให้เริ่มเดินทางผ่านสตริงจากตัวอักษรสุดท้ายทีละตัว ตรวจสอบว่าความถี่ที่เก็บไว้เป็น 1 หรือไม่ ถ้าเป็น 1 ให้คืนค่า มิฉะนั้นไปตัวก่อนหน้า

ตัวอย่าง

#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