এই সমস্যাতে, আমাদের একটি স্ট্রিং দেওয়া আছে। এবং Q সংখ্যক কোয়েরি, প্রতিটিতে দুটি পূর্ণসংখ্যা l এবং r এবং একটি ক্যারেক্টার ch থাকে। আমাদের কাজ হলো C++-এ সাবস্ট্রিং-এ ক্যারেক্টার ফ্রিকোয়েন্সির কোয়েরি সমাধান করার প্রোগ্রাম লিখা।
সমস্যা বর্ণনা: এখানে প্রতিটি কোয়েরির জন্য, সাবস্ট্রিং str[l...r]-এ ক্যারেক্টার 'ch'-এর ফ্রিকোয়েন্সি বের করতে হবে।
উদাহরণ দিয়ে বুঝি,
ইনপুট
str = "tutorialspoint" Q = 2 0 6 t 5 13 i
আউটপুট
2 2
ব্যাখ্যা
কোয়েরি ১ − সাবস্ট্রিং হলো "tutoria", ক্যারেক্টার t ২বার আসেছে।
কোয়েরি ২ − সাবস্ট্রিং হলো "ialspoint", ক্যারেক্টার i ২বার আসেছে।
সমাধান পদ্ধতি
সমস্যা সমাধানের সহজ এবং সরল পদ্ধতি হচ্ছে প্রতিটি কোয়েরির জন্য স্ট্রিং-কে 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<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is "<<CalcCharFreq(str, queries[i])<<"\n";
return 0;
}আউটপুট
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2
আরেকটি পদ্ধতি হচ্ছে প্রি-কম্পিউটেড অ্যারে ব্যবহার করা। এখানে আমরা একটি ২D অ্যারে তৈরি করব যা প্রতিটি ইনডেক্স পর্যন্ত ক্যারেক্টার ফ্রিকোয়েন্সি সংরক্ষণ করবে। যেমন freq[3][2] ইনডেক্স ২-এ 'c' ক্যারেক্টারের ফ্রিকোয়েন্সি রাখবে। প্রাথমিকভাবে সব ফ্রিকোয়েন্সি ০।
তারপর আমরা প্রতিটি ইনডেক্সের জন্য ক্যারেক্টার ফ্রিকোয়েন্সি প্রি-কম্পিউট করব। এরপর রেঞ্জের ফ্রিকোয়েন্সি বের করার জন্য ইনডেক্স 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<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is "
<<CalcCharFreq( queries[i])<<"\n";
return 0;
}আউটপুট
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2
