এই সমস্যায়, আমাদের একটি স্ট্রিং str এবং Q কোয়েরি দেওয়া আছে, প্রতিটি দুটি ইন্টিজার নিয়ে গঠিত। আমাদের কাজ হল দেওয়া স্ট্রিং-এর সাবস্ট্রিং-এ শেষ নন-রিপিটিং ক্যারেক্টার খুঁজে বের করার প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
প্রতিটি কোয়েরিতে দুটি ইন্টিজার L এবং R থাকে। কোয়েরি সমাধান করতে, আমরা ইনডেক্স L থেকে R পর্যন্ত একটি সাবস্ট্রিং নেব। এবং সাবস্ট্রিং-এ শেষ নন-রিপিটিং ক্যারেক্টারটি খুঁজে বের করব।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: str = "Tutorialspoint" Q = 2
query = {{4, 8}, {2, 6}}
আউটপুট: -1 , -1
ব্যাখ্যা
subStr[4...8] = "rials"। শেষ নন-রিপিটিং ক্যারেক্টার হল s। কিন্তু সকল ক্যারেক্টারের ফ্রিকোয়েন্সি ১।
subStr[2...6] = "toria"। শেষ নন-রিপিটিং ক্যারেক্টার হল a। কিন্তু সকল ক্যারেক্টারের ফ্রিকোয়েন্সি ১।
সমাধান পদ্ধতি
সমস্যা সমাধান করতে, আমাদের ফ্রিকোয়েন্সি ১ বিশিষ্ট ক্যারেক্টার খুঁজে বের করতে হবে। এর জন্য একটি সহজ পদ্ধতি হল charFreq[][] ম্যাট্রিক্স তৈরি করা। সাবঅ্যারে কোয়েরি সমাধান করতে, আমরা সকল ক্যারেক্টারের ফ্রিকোয়েন্সি চেক করব এবং ফ্রিকোয়েন্সি ১ বিশিষ্ট শেষ ক্যারেক্টার ফেরত দিব।
C++ প্রোগ্রাম উদাহরণ
#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
