এই সমস্যায়, আমাদের স্ট্রিং স্ট্র এবং Q প্রশ্ন দেওয়া হয়েছে, প্রতিটিতে দুটি পূর্ণসংখ্যা রয়েছে। আমাদের কাজ হল C++ এ প্রদত্ত স্ট্রিং-এর সাব-স্ট্রিং-এ শেষ অ-পুনরাবৃত্ত অক্ষর খুঁজে বের করার জন্য কোয়েরির সমাধান করার জন্য প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
প্রতিটি ক্যোয়ারীতে, আমাদের দুটি পূর্ণসংখ্যা L এবং R রয়েছে। প্রশ্নগুলি সমাধান করার জন্য, আমরা সূচক L থেকে সূচক R পর্যন্ত একটি সাবস্ট্রিং নেব। এবং শেষ অক্ষরটি খুঁজে বের করব যেটি সাব-স্ট্রিং-এ পুনরাবৃত্তি হচ্ছে না।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট :str =“Tutorialspoint” Q =2
প্রশ্ন ={{4, 8}, {2, 6}}
আউটপুট :-1 , -1
ব্যাখ্যা
subStr[4...8] ="রিয়ালস"। শেষ অ-পুনরাবৃত্ত অক্ষর হল s. কিন্তু সমস্ত অক্ষরের ফ্রিকোয়েন্সি 1।
subStr[2...6] ="টোরিয়া"। শেষ অ-পুনরাবৃত্ত অক্ষর হল a. কিন্তু সমস্ত অক্ষরের ফ্রিকোয়েন্সি 1।
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমাদের একটি একক কম্পাঙ্কের সাথে অক্ষরটি খুঁজে বের করতে হবে। এর জন্য, একটি সহজ এবং সহজ পদ্ধতি হল charFreq[][] গণনা করার জন্য একটি ম্যাট্রিক্স তৈরি করা। সাব্যারে কোয়েরি সমাধান করার জন্য, আমরা সমস্ত অক্ষরের সংঘটনের ফ্রিকোয়েন্সি পরীক্ষা করব এবং শেষ অক্ষরটি ফ্রিকোয়েন্সি 1 দিয়ে ফেরত দেব।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int charFreq[256][1000] = {0};
void initialiseCharFrequency(string str, int n) {
charFreq[(int)str[0]][0] = 1;
for (int i = 1; i < n; i++) {
char ch = str[i];
for (int j = 0; j < 256; j++) {
char charToUpdate = (char)j;
if (charToUpdate == ch)
charFreq[j][i] = charFreq[j][i - 1] + 1;
else
charFreq[j][i] = charFreq[j][i - 1];
}
}
}
string returnCharFromString(char x) {
string s(1, x);
return s;
}
string lastUniqueChar(string str, int n, int start, int end) {
for (int i = end; i >= start; i--) {
char ch = str[i];
if ((charFreq[(int)ch][end] - charFreq[(int)ch][start - 1]) ==1)
return returnCharFromString(ch);
}
return "-1";
}
int main() {
string str = "TutorialsPoint";
int len = str.length();
int Q = 3;
int query[Q][2] = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
initialiseCharFrequency(str, len);
for (int i = 0; i < Q; i++)
cout<<"\nFor Query "<<(i+1)<<": The last non-repeating character in the sub-string of a given string is "<<lastUniqueChar(str, len,query[i][0], query[i][1]);
} আউটপুট
For Query 1: The last non-repeating character in the sub-string of a given string is P For Query 2: The last non-repeating character in the sub-string of a given string is o For Query 3: The last non-repeating character in the sub-string of a given string is n
