मान लीजिए कि हमारे पास दो तार S और T हैं, S की लंबाई n है, और T की लंबाई n + 1 है। T उन सभी वर्णों को धारण करेगा जो S में मौजूद हैं, लेकिन इसमें एक अतिरिक्त वर्ण होगा। हमारा काम कुछ कुशल दृष्टिकोण का उपयोग करके अतिरिक्त चरित्र को खोजना है।
इस समस्या को हल करने के लिए, हम एक खाली हैश तालिका लेंगे, और दूसरी स्ट्रिंग के सभी वर्णों को सम्मिलित करेंगे, फिर प्रत्येक वर्ण को पहली स्ट्रिंग से हटा देंगे, शेष वर्ण एक अतिरिक्त वर्ण है।
उदाहरण
#include<iostream>
#include<unordered_map>
using namespace std;
char getExtraCharacter(string S, string T) {
unordered_map<char, int> char_map;
for (int i = 0; i < T.length(); i++)
char_map[T[i]]++;
for (int i = 0; i < S.length(); i++)
char_map[S[i]]--;
for (auto item = char_map.begin(); item != char_map.end(); item++) {
if (item->second == 1)
return item->first;
}
}
int main() {
string S = "PQRST";
string T = "TUQPRS";
cout << "Extra character: " << getExtraCharacter(S, T);
} आउटपुट
Extra character: U