समस्या विवरण
इस समस्या में, हमें एक स्ट्रिंग दी गई है। और Q क्वेरीज़ जिनमें से प्रत्येक में दो पूर्णांक l और r और वर्ण ch होता है। हमारा कार्य C++ में उपस्ट्रिंग में वर्णों की आवृत्ति के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है।
यहां प्रत्येक क्वेरी के लिए, हम सबस्ट्रिंग str[l...r] में वर्ण 'ch' की घटना की आवृत्ति ढूंढेंगे।
उदाहरण
इनपुट
str = "tutorialspoint" Q = 2 0 6 t 5 13 i
आउटपुट
2 2
व्याख्या
क्वेरी 1 के लिए - सबस्ट्रिंग "tutoria" है, वर्ण t 2 बार आता है।
क्वेरी 2 के लिए - सबस्ट्रिंग "ialspoint" है, वर्ण i 2 बार आता है।
समाधान दृष्टिकोण
समस्या को हल करने का आसान और सीधा दृष्टिकोण प्रत्येक क्वेरी के लिए स्ट्रिंग को l से r तक पार करना और स्ट्रिंग में वर्ण ch की घटना को गिनना है।
कार्यक्रम उदाहरण (सरल दृष्टिकोण)
#include <bits/stdc++.h>
using namespace std;
struct Query{
int l, r;
char ch;
};
int CalcCharFreq(string str, Query queries){
int count = 0;
for(int i = queries.l; i < queries.r; i++){
if(str[i] == queries.ch )
count++;
}
return count;
}
int main(){
string str = "tutorialspoint";
int Q = 2;
Query queries[Q];
queries[0].l = 0;
queries[0].r = 5;
queries[0].ch = 't';
queries[1].l = 5;
queries[1].r = 13;
queries[1].ch = 'i';
for(int i = 0; i<Q; i++)
cout << "क्वेरी " << (i+1) << ": वर्ण '" << queries[i].ch << "' की आवृत्ति " << CalcCharFreq(str, queries[i]) << "\n";
return 0;
}
आउटपुट
क्वेरी 1: वर्ण 't' की आवृत्ति 2 क्वेरी 2: वर्ण 'i' की आवृत्ति 2
दूसरा दृष्टिकोण समस्या को हल करने के लिए पूर्व-गणना सरणी (pre-computed array) का उपयोग करना है। यहां, हम एक 2D सरणी बनाएंगे जो उस विशिष्ट इंडेक्स तक वर्णों की आवृत्ति को संग्रहीत करेगी यानी freq[3][2] इंडेक्स 2 पर वर्ण 'c' की आवृत्ति को संग्रहीत करेगा। प्रारंभ में, सभी आवृत्तियाँ 0 हैं।
फिर, हम प्रत्येक इंडेक्स मान पर वर्ण की आवृत्ति की पूर्व-गणना करेंगे। उसके बाद, हम इंडेक्स l पर घटना की आवृत्ति को इंडेक्स r पर घटना की आवृत्ति से घटाकर रेंज में वर्ण की आवृत्ति ढूंढेंगे।
कार्यक्रम उदाहरण (पूर्व-गणना दृष्टिकोण)
#include <bits/stdc++.h>
using namespace std;
int charFreq[100][26];
struct Query{
int l, r;
char ch;
};
void countCharFreq(string str, int size){
memset(charFreq, 0, sizeof(int));
for (int i = 0; i < size; i++){
charFreq[i][str[i] - 'a']++;
}
for (int i = 1; i < size; i++) {
for (int j = 0; j < 26; j++)
charFreq[i][j] += charFreq[i - 1][j] ;
}
}
int CalcCharFreq(Query queries){
return charFreq[queries.r][queries.ch - 'a'] - charFreq[queries.l][queries.ch - 'a'];
}
int main(){
string str = "tutorialspoint";
int size = str.length();
int Q = 2;
countCharFreq(str, size);
Query queries[Q];
queries[0].l = 1;
queries[0].r = 13;
queries[0].ch = 't';
queries[1].l = 4;
queries[1].r = 13;
queries[1].ch = 'i';
for(int i = 0; i<Q; i++)
cout << "क्वेरी " << (i+1) << ": वर्ण '" << queries[i].ch << "' की आवृत्ति "
<< CalcCharFreq(queries[i]) << "\n";
return 0;
}
आउटपुट
क्वेरी 1: वर्ण 't' की आवृत्ति 2 क्वेरी 2: वर्ण 'i' की आवृत्ति 2
