আমরা একটি স্ট্রিং str দেওয়া হয়. লক্ষ্য হল str এর সাবস্ট্রিংগুলির সংখ্যা গণনা করা যাতে প্রতিটি অক্ষর সর্বাধিক k বার হয়। উদাহরণস্বরূপ যদি ইনপুট হয় “abc” এবং k=1, তাহলে সাবস্ট্রিংগুলি হবে “a”, “b”, “c”, “ab”, “bc”, “abc”।
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − str="abaefgf"
আউটপুট − একই প্রথম এবং শেষ অক্ষর সহ সাবস্ট্রিংগুলির সংখ্যা হল &mmius; ৯
ব্যাখ্যা − সাবস্ট্রিং হবে
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
ইনপুট − str="abcdef"
আউটপুট − একই প্রথম এবং শেষ অক্ষর সহ সাবস্ট্রিংগুলির সংখ্যা হল:6
ব্যাখ্যা − সাবস্ট্রিং হবে -
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
প্রদত্ত সমস্যা সমাধানের জন্য একাধিক পন্থা হতে পারে যেমন নিষ্পাপ দৃষ্টিভঙ্গি এবং দক্ষ পদ্ধতি। সুতরাং আসুন প্রথমে নিষ্পাপ পদ্ধতির দিকে তাকাই। আমরা প্রতিটি দৈর্ঘ্যের সাবস্ট্রিংগুলিকে একটি ফাংশন চেক() এ পাস করব। যদি সেই সাবস্ট্রিং একই অক্ষর দিয়ে শুরু হয় এবং শেষ হয় তাহলে গণনা বৃদ্ধি করুন।
-
স্ট্রিং str নিন. str.size().
হিসাবে দৈর্ঘ্য গণনা করুন -
ফাংশন চেক (স্ট্রিং স্ট্র) সাবস্ট্রিং স্ট্র নেয় এবং এটি প্রথম এবং শেষ অক্ষর একই কিনা তা পরীক্ষা করে। ( str[0]==str[দৈর্ঘ্য-1])। সত্য হলে, 1 ফেরত দিন।
-
ফাংশন check_Start_End(string str, int length) str এবং এর দৈর্ঘ্য ইনপুট হিসাবে নেয় এবং str এর সাবস্ট্রিংগুলির গণনা প্রদান করে যা একই অক্ষর দিয়ে শুরু এবং শেষ হয়।
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
লুপের জন্য দুই ব্যবহার করে ট্রাভার্স str। i=0 থেকে i<দৈর্ঘ্য এবং ভিতরের j=1 থেকে j=দৈর্ঘ্য-1।
-
আমরা সমস্ত দৈর্ঘ্যের substr(i,j) ব্যবহার করে সমস্ত সাবস্ট্রিং পাব। চেক করতে প্রতিটি সাবস্ট্রিং পাস করুন()। যদি এটি 1 রিটার্ন করে, তাহলে ইনক্রিমেন্ট কাউন্ট।
-
উভয়ের শেষে লুপ গণনাতে একই শুরু এবং শেষ অক্ষর সহ str এর অনেকগুলি সাবস্ট্রিং থাকবে৷
-
পছন্দসই ফলাফল হিসাবে রিটার্ন গণনা করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int count_k(string str, int len, int k){
int count = 0;
int arr[26];
for (int i = 0; i < len; i++){
memset(arr, 0, sizeof(arr));
for (int j = i; j < len; j++){
arr[str[j] - 'a']++;
if (arr[str[j] - 'a'] <= k)
{ count++; }
else
{ break; }
}
}
return count;
}
int main(){
string str = "bbddehj";
int k = 1;
int length = str.length();
cout<<"Count of substrings with each character occurring at most k times are: "<<count_k(str,
length, k);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে -
Count of substrings with each character occurring at most k times are: 14
