ค้นหาอักขระที่ซ้ำกันก่อนเป็นสตริงใน C++

สมมติว่าเรามีสตริง เราต้องหาตัวอักษรตัวแรกที่ซ้ำกัน ดังนั้นสตริงคือ "Hello Friends" อักขระตัวแรกที่ซ้ำกันจะเป็น l เนื่องจากมีสองอันต่อกัน

ในการแก้ปัญหานี้ เราจะใช้เทคนิคการแฮช สร้างตารางแฮชหนึ่งตาราง สแกนอักขระแต่ละตัวทีละตัว หากไม่มีอักขระอยู่ จากนั้นแทรกลงในตารางแฮช หากมีอยู่แล้ว ให้ส่งคืนอักขระนั้น

ตัวอย่าง

#include<iostream>
#include<unordered_set>
using namespace std;
char getFirstRepeatingChar(string &s) {
   unordered_set<char> hash;
   for (int i=0; i<s.length(); i++) {
      char c = s[i];
      if (hash.find(c) != hash.end())
         return c;
      else
         hash.insert(c);
   }
   return '\0';
}
int main () {
   string str = "Hello Friends";
   cout << "First repeating character is: " << getFirstRepeatingChar(str);
}

ผลลัพธ์

First repeating character is: l