আমাদেরকে শুধুমাত্র 'a', 'b' এবং 'c' সম্বলিত একটি স্ট্রিং str[] দেওয়া হয়েছে। লক্ষ্য হল str[] এর সাবস্ট্রিং খুঁজে বের করা যাতে তিনটি অক্ষরই সেই সাবস্ট্রিং এর অংশ না হয়। যেকোনো স্ট্রিং str এর জন্য, সাবস্ট্রিং হতে পারে “a”, “b”, “c”, “abb”, “bba”, “bc”, “ca”, “ccc” কিন্তু “abc”, “bcca”, “না” cab” এর মধ্যে 'a', 'b' এবং 'c', তিনটিই আছে।
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − str[] =“aabc”
আউটপুট − সাব-স্ট্রিংগুলির সংখ্যা যেখানে একই সময়ে সেট {‘a’, ‘b’, ‘c’} থেকে সমস্ত অক্ষর থাকে না −8
ব্যাখ্যা − সাবস্ট্রিং হবে:“a”, “a”, “b”, “c”, “aa”, “ab”, “bc”, “aab”
ইনপুট − str[] =“abcabc”
আউটপুট − সাব-স্ট্রিংগুলির গণনা যেখানে একই সময়ে সেট {'a', 'b', 'c'} থেকে সমস্ত অক্ষর থাকে না তা হল −11
ব্যাখ্যা − সাবস্ট্রিংগুলি হবে:“a”, “b”, “c”, “a”, “b”, “c”, “ab”, “bc”, “ca”, “ab”, “bc”
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা জানি যে n অক্ষর সহ স্ট্রিং এর মোট সাবস্ট্রিং সংখ্যা হল n*(n+1)/2।
আমরা এখন স্ট্রিংটি অতিক্রম করব এবং প্রতিটি ধরনের অক্ষর ‘a’, ‘b’ বা ‘c’-এর জন্য। আমরা অন্য দুটি অক্ষর ('b','c'), ('c','a') এবং ('a', 'b') এর পূর্ববর্তী সূচীগুলি পরীক্ষা করব। শুধুমাত্র গণনা থেকে অন্য দুটির ন্যূনতম সূচী বিয়োগ করুন কারণ আমরা জানি যে আমরা বর্তমান অক্ষরটিকে সাবস্ট্রিং-এ অন্তর্ভুক্ত করার জন্য সেই অক্ষরটিকে সরিয়ে দিচ্ছি যাতে এতে তিনটিই না থাকে৷
-
একটি অক্ষর অ্যারে হিসাবে একটি স্ট্রিং স্ট্র নিন৷
-
ফাংশন sub_without_all(char str[], int সাইজ) একটি স্ট্রিং নেয়, এটির দৈর্ঘ্য এবং 'a', 'b' এবং 'c' একসাথে নেই এমন সাবস্ট্রিংগুলির গণনা প্রদান করে।
-
str[] এর সম্ভাব্য সকল সাবস্ট্রিং এর সংখ্যার জন্য প্রাথমিক গণনার আকার*(আকার+1)/2 নিন।
-
str[] এ 'a', 'b', 'c' এর শেষ সূচক সংরক্ষণ করতে a,b,c ভেরিয়েবল নিন। 0 দিয়ে সব শুরু করুন।
-
i=0 থেকে i
-
যদি str[i]==’a’ a=i+1 হিসাবে ‘a’-এর সূচক আপডেট করে। সাবস্ট্রিং-এ 'a' অন্তর্ভুক্ত করতে গণনা থেকে 'b' বা 'c'-এর ন্যূনতম সূচক বিয়োগ করুন। গণনা থেকে যেটি ন্যূনতম হয় b,c বিয়োগ করুন।
-
str[i]==’b’ বা str[i]==’c’ এর জন্য আগের ধাপের মতই করুন।
-
শেষে আমরা str[] এর সাবস্ট্রিং হিসাবে গণনা করেছি যেগুলি একসাথে তিনটি অক্ষর ছাড়াই৷
-
ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
int update_size = size * (size + 1);
int count = update_size / 2;
int a, b, c;
a = b = c = 0;
for (int i = 0; i < size; i++){
if (str[i] == 'a'){
a = i + 1;
count -= min(b, c);
}
else if (str[i] == 'b'){
b = i + 1;
count -= min(a, c);
}
else{
c = i + 1;
count -= min(a, b);
}
}
return count;
}
int main(){
char str[] = "abcabbc";
int size = strlen(str);
cout<<"Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at
the same time are: "<<sub_without_all(str, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at the same time are: 15 