ধরি দুটি স্ট্রিং 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
