সমস্যা বিবরণ
একটি স্ট্রিং দেওয়া আছে। স্ট্রিংকে প্যালিনড্রোম बनाने অ্যাপেন্ড করার মিনিমাম ক্যারেক্টার বের করুন।
উদাহরণ
যদি স্ট্রিং = "abcac" হয়, তবে ২টি হাইলাইটেড ক্যারেক্টার অ্যাপেন্ড করে প্যালিনড্রোম বানানো যায়: "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
