Giả sử chúng ta có một chuỗi; chúng ta phải tìm ký tự đầu tiên bị lặp lại. Vì vậy nếu chuỗi là "Hello Friends", ký tự lặp lại đầu tiên sẽ là l. Vì có hai chữ l liên tiếp nhau.
Để giải quyết bài toán này, chúng ta sẽ sử dụng kỹ thuật hashing. Tạo một bảng băm, quét từng ký tự một, nếu ký tự chưa có thì chèn vào bảng băm, nếu đã có thì trả về ký tự đó.
Ví dụ
#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); }
Kết quả
First repeating character is: l