এই সমস্যায়, আমাদের শুধুমাত্র a এবং b এবং একটি পূর্ণসংখ্যা N সম্বলিত স্ট্রিং দেওয়া হয়েছে যাতে str n বার যুক্ত করে একটি স্ট্রিং তৈরি করা হয়। আমাদের কাজ হল মোট সাবস্ট্রিং সংখ্যা মুদ্রণ করা যেখানে a'-এর গণনা b-এর গণনার চেয়ে বেশি।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
Input: aab 2 Output: 9 Explanation: created string is aabaab. Substrings with count(a) > count(b) : ‘a’ , ‘aa’, ‘aab’, ‘aaba’, ‘aabaa’, ‘aabaab’, ‘aba’, ‘baa’, ‘abaa’.
এই সমস্যাটি সমাধান করার জন্য, আমাদের স্ট্রিংটিতে প্রয়োজনীয় উপসর্গ উপসেট রয়েছে কিনা তা পরীক্ষা করতে হবে। এখানে, আমরা স্ট্রিং স্ট্রিংটি সম্পূর্ণ সংস্করণ নয় তা পরীক্ষা করব। এখানে, w উপসর্গের উপর ভিত্তি করে স্ট্রিং পরীক্ষা করবে এবং a এবং b এর সংঘটনের সংখ্যা।
এই প্রোগ্রামটি আমাদের সমাধানের বাস্তবায়ন দেখাবে
উদাহরণ
#include <iostream>
#include <string.h>
using namespace std;
int prefixCount(string str, int n){
int a = 0, b = 0, count = 0;
int i = 0;
int len = str.size();
for (i = 0; i < len; i++) {
if (str[i] == 'a')
a++;
if (str[i] == 'b')
b++;
if (a > b) {
count++;
}
}
if (count == 0 || n == 1) {
cout<<count;
return 0;
}
if (count == len || a - b == 0) {
cout<<(count*n);
return 0;
}
int n2 = n - 1, count2 = 0;
while (n2 != 0) {
for (i = 0; i < len; i++) {
if (str[i] == 'a')
a++;
if (str[i] == 'b')
b++;
if (a > b)
count2++;
}
count += count2;
n2--;
if (count2 == 0)
break;
if (count2 == len) {
count += (n2 * count2);
break;
}
count2 = 0;
}
return count;
}
int main() {
string str = "aba";
int N = 2;
cout<<"The string created by using '"<<str<<"' "<<N<<" times has ";
cout<<prefixCount(str, N)<<" substring with count of a greater than count of b";
return 0;
} আউটপুট
The string created by using 'aba' 2 times has 5 substring with count of a greater than count of b
