C++ में दी गई स्ट्रिंग के सबस्ट्रिंग में अंतिम गैर-दोहराने वाला वर्ण ढूंढने की क्वेरी

इस समस्या में, हमें एक स्ट्रिंग str और Q क्वेरी दी गई हैं, जिनमें प्रत्येक में दो पूर्णांक हैं। हमारा कार्य C++ में दी गई स्ट्रिंग के सबस्ट्रिंग में अंतिम गैर-दोहराने वाले वर्ण को ढूंढने की क्वेरी को हल करने के लिए प्रोग्राम बनाना है।

समस्या विवरण

प्रत्येक क्वेरी में, हमारे पास दो पूर्णांक L और R हैं। क्वेरी को हल करने के लिए, हम इंडेक्स L से इंडेक्स R से शुरू होने वाला एक सबस्ट्रिंग लेंगे। और सब-स्ट्रिंग में अंतिम वर्ण ढूंढेंगे जो गैर-दोहराने वाला है।

उदाहरण से समझते हैं

इनपुट: str = "Tutorialspoint" Q = 2

query = {{4, 8}, {2, 6}}

आउटपुट: -1, -1

व्याख्या

subStr[4...8] = "rials"। अंतिम गैर-दोहराने वाला वर्ण s है। लेकिन सभी वर्णों की फ्रीक्वेंसी 1 है।

subStr[2...6] = "toria"। अंतिम गैर-दोहराने वाला वर्ण a है। लेकिन सभी वर्णों की फ्रीक्वेंसी 1 है।

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हमें एकल घटना आवृत्ति वाले वर्ण को ढूंढना होगा। इसके लिए, एक आसान और सरल दृष्टिकोण charFreq[][] की गणना के लिए एक मैट्रिक्स बनाना है। सबएरे क्वेरी को हल करने के लिए, हम सभी वर्णों की घटना की फ्रीक्वेंसी की जांच करेंगे और फ्रीक्वेंसी 1 वाले अंतिम वर्ण को वापस करेंगे।

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