আমাদের একটি স্ট্রিং str দেওয়া আছে। লক্ষ্য হলো str-এ কতগুলো সাবস্ট্রিং আছে যাতে প্রতিটি ক্যারেক্টার সর্বোচ্চ k বার আয়ত্ত হয়। উদাহরণস্বরূপ, ইনপুট "abc", k=1 হলে সাবস্ট্রিং: "a", "b", "c", "ab", "bc", "abc"।
উদাহরণ দিয়ে বুঝি
ইনপুট − str="abaefgf"
আউটপুট − প্রতিটি ক্যারেক্টার সর্বোচ্চ k বার আয়ত্ত সাবস্ট্রিং: ৯
ব্যাখ্যা − সাবস্ট্রিং: "a", "b", "a", "e", "f", "g", "f", "aba", "fgf"। মোট ৯।
ইনপুট − str="abcdef"
আউটপুট − প্রতিটি ক্যারেক্টার সর্বোচ্চ k বার আয়ত্ত সাবস্ট্রিং: ৬
ব্যাখ্যা − সাবস্ট্রিং: "a", "b", "c", "d", "e", "f"। মোট ৬।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই সমস্যা সমাধানের একাধিক পদ্ধতি আছে: নেভ הפשט এবং দক্ষ পদ্ধতি। প্রথমে নেভ הפשט পদ্ধতি দেখি। প্রতিটি দৈর্ঘ্যের সাবস্ট্রিং check() ফাংশনে পাস করব। যদি সাবস্ট্রিং-এর প্রথম এবং শেষ ক্যারেক্টার একই হয়, কাউন্ট বাড়াব।
- স্ট্রিং
str। দৈর্ঘ্যstr.size()। check(string str)ফাংশন সাবস্ট্রিং নিয়ে প্রথম ও শেষ ক্যারেক্টার একই কিনা চেক করে (str[0]==str[length-1])। সত্য হলে ১ রিটার্ন।check_Start_End(string str, int length)ফাংশন স্ট্রিং এবং দৈর্ঘ্য নিয়ে একই শুরু-শেষ ক্যারেক্টার সাবস্ট্রিং কাউন্ট রিটার্ন করে।- প্রাথমিক কাউন্ট ০।
- দুটি
forলুপ:i=0থেকেlength, ইনারj=1থেকেlength-1। substr(i,j)দিয়ে সব দৈর্ঘ্যের সাবস্ট্রিং পান।check()-এ পাস করুন। ১ রিটার্ন করলে কাউন্ট বাড়ান।- দুই লুপ শেষে
countরিটার্ন করুন।
দক্ষ পদ্ধতি (Efficient Approach)
দক্ষ পদ্ধতিতে ফрикোয়েন্সি অ্যারে ব্যবহার করা হয়। প্রতিটি সাবস্ট্রিংয়ের জন্য ফрикোয়েন্সি অ্যারে রিসেট করে চেক করা হয়।
count_k(string str, int len, int k)ফাংশন স্ট্রিং, দৈর্ঘ্য, k নিয়ে কাউন্ট রিটার্ন করে।i=0থেকেlenপর্যন্ত লুপে:memset(arr, 0, sizeof(arr))দিয়ে ফрикোয়েন্সি অ্যারে রিসেট।j=iথেকেlenপর্যন্ত লুপে:arr[str[j]-'a']++।- যদি
arr[str[j]-'a'] <= kহয়,count++। অন্যথায় ব্রেক।
countরিটার্ন করুন।
উদাহরণ
#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
