ধরুন আমাদের দুটি স্ট্রিং 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
