সমস্যা বিবৃতি
একটি স্ট্রিং দেওয়া হয়েছে, একটি স্ট্রিং প্যালিনড্রোম তৈরি করতে ন্যূনতম অক্ষরগুলি যুক্ত করতে হবে৷
উদাহরণ
যদি স্ট্রিং abcac হয় তাহলে আমরা 2টি হাইলাইড অক্ষর যেমন abcacba যোগ করে স্ট্রিং প্যালিনড্রোম তৈরি করতে পারি।
অ্যালগরিদম
- পরীক্ষা করুন যে স্ট্রিংটি ইতিমধ্যেই প্যালিনড্রোম কিনা, যদি হ্যাঁ হয় তবে কোনও অক্ষর যুক্ত করার দরকার নেই৷
- একের পর এক স্ট্রিং থেকে একটি অক্ষর মুছে ফেলুন এবং বাকি স্ট্রিং প্যালিনড্রোম কিনা তা পরীক্ষা করুন
- স্ট্রিং প্যালিড্রোম না হওয়া পর্যন্ত উপরের প্রক্রিয়াটি পুনরাবৃত্তি করুন
- একটি চূড়ান্ত উত্তর হিসাবে এখন পর্যন্ত সরানো অক্ষরের সংখ্যা ফেরত দিন
উদাহরণ
#include <iostream>
#include <cstring>
using namespace std;
bool isPalindrome(char *str) {
int n = strlen(str);
if (n == 1) {
return true;
}
int start = 0, end = n - 1;
while (start < end) {
if (str[start] != str[end]) {
return false;
}
++start;
--end;
}
return true;
}
int requiredAppends(char *str) {
if (isPalindrome(str)) {
return 0;
}
return 1 + requiredAppends(str + 1);
}
int main() {
char *str = "abcac";
cout << "Characters to be appended = " << requiredAppends(str) << endl;
return 0;
} আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেCharacters to be appended = 2
