इस समस्या में, हमें स्ट्रिंग str, और Q प्रश्न दिए गए हैं, जिनमें से प्रत्येक में दो पूर्णांक हैं। हमारा कार्य C++ में दिए गए स्ट्रिंग के उप-स्ट्रिंग में अंतिम गैर-दोहराए जाने वाले वर्ण को खोजने के लिए क्वेरीज़ को हल करने के लिए प्रोग्राम बनाना है।
समस्या का विवरण
प्रत्येक क्वेरी में, हमारे पास दो पूर्णांक L और R होते हैं। प्रश्नों को हल करने के लिए, हम इंडेक्स L से इंडेक्स R तक एक सबस्ट्रिंग लेंगे। और अंतिम कैरेक्टर को खोजें जो सब-स्ट्रिंग में नॉन-रिपीटिंग है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :str ="ट्यूटोरियल पॉइंट" Q =2
क्वेरी ={{4, 8}, {2, 6}}
आउटपुट :-1 , -1
स्पष्टीकरण
सबस्ट्र [4...8] ="रियाल"। अंतिम गैर-दोहराए जाने वाला वर्ण s है। लेकिन सभी वर्णों की आवृत्ति 1 होती है।
सबस्ट्र [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. है