สมมติว่าเรามีสตริง str เราต้องหาอักขระที่ไม่ซ้ำตัวสุดท้ายในนั้น ดังนั้นหากสตริงอินพุตเป็นเหมือน "การเขียนโปรแกรม" ดังนั้นอักขระที่ไม่ซ้ำตัวแรกคือ 'n' หากไม่มีอักขระดังกล่าว ให้คืนค่า -1
เราสามารถแก้ปัญหานี้ได้โดยสร้างอาร์เรย์ความถี่เดียว ซึ่งจะเก็บความถี่ของอักขระแต่ละตัวของสตริงที่กำหนด เมื่อความถี่ได้รับการอัปเดตแล้ว ให้เริ่มสำรวจสตริงจากอักขระตัวสุดท้ายทีละตัว จากนั้นตรวจสอบว่าความถี่ที่เก็บไว้เป็น 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
