আমাদের একটি স্ট্রিং str দেওয়া আছে। লক্ষ্য হলো str-এর সব সাবস্ট্রিং যেগুলো বিশেষ প্যালিনড্রোম (special palindrome) এবং দৈর্ঘ্য ১ এর চেয়ে বড়, তাদের সংখ্যা বের করা। বিশেষ প্যালিনড্রোম হলো এমন স্ট্রিং যেগুলো або সব ক্যারেক্টর একই, অথবা শুধু মাঝপথের ক্যারেক্টর ভিন্ন। উদাহরণস্বরূপ, স্ট্রিং "baabaa" হলে বিশেষ প্যালিনড্রোম সাবস্ট্রিং গুলো: "aa", "aabaa", "aba", "aa"।
উদাহরণ দিয়ে বুঝি
ইনপুট − str="abccdcdf"
আউটপুট − স্ট্রিং-এ বিশেষ প্যালিনড্রোম সংখ্যা: ৩
ব্যাখ্যা − বিশেষ প্যালিনড্রোম সাবস্ট্রিং গুলো: "cc", "cdc", "dcd"
ইনপুট − str="baabaab"
আউটপুট − স্ট্রিং-এ বিশেষ প্যালিনড্রোম সংখ্যা: ৪
ব্যাখ্যা − বিশেষ প্যালিনড্রোম সাবস্ট্রিং গুলো: "aa", "aabaa", "aba", "aa"
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- অ্যালফাবেটের স্ট্রিং তৈরি করুন এবং দৈর্ঘ্য বের করুন। ডেটা ফাংশনে পাস করুন।
- অস্থায়ী ভেরিয়েবল
countএবংi০ দিয়ে ইনিশিয়ালাইজ করুন। - স্ট্রিং দৈর্ঘ্যের সাইজের একটি অ্যারে
arrতৈরি করুন এবং ০ দিয়ে ইনিশিয়ালাইজ করুন। whileলুপ চলবেi < lenপর্যন্ত।- লুপের ভিতরে
total = 1এবংj = i + 1সেট করুন। - আরেকটি
whileলুপ চলবেstr[i] == str[j] && j < lenপর্যন্ত। - লুপের ভিতরে
total++এবংj++করুন। count += (total * (total + 1) / 2),arr[i] = total,i = jসেট করুন।forলুপj=1থেকেlen-1পর্যন্ত চলবে।- যদি
str[j] == str[j-1]হয়, তবেarr[j] = arr[j-1]সেট করুন। temp = str[j-1]সেট করুন এবং চেক করুন:j > 0 && j < (len-1) && temp == str[j+1] && str[j] != temp। সত্য হলেcount += min(arr[j-1], arr[j+1])।count = count - lenকরুন।countরিটার্ন করুন।- ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len) {
int count = 0, i = 0;
int arr[len] = { 0 };
while (i < len) {
int total = 1;
int j = i + 1;
while (str[i] == str[j] && j < len) {
total++;
j++;
}
count += (total * (total + 1) / 2);
arr[i] = total;
i = j;
}
for (int j = 1; j < len; j++) {
if (str[j] == str[j - 1]) {
arr[j] = arr[j - 1];
}
int temp = str[j - 1];
if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)) {
count += min(arr[j-1], arr[j+1]);
}
}
count = count - len;
return count;
}
int main() {
string str = "bcbaba";
int len = str.length();
cout << "Count of special palindromes in a String are: " << count_palindromes(str, len);
return 0;
}
আউটপুট
Count of special palindromes in a String are: 3
