দুটি সমান দৈর্ঘ্যের স্ট্রিং 'a' এবং 'b' দেওয়া আছে। সেগুলো কোনো ইনডেক্সে বিভক্ত করলে প্রিফিক্স + সাফিক্স কানবিনেশন প্যালিনড্রোম বানাবে কিনা চেক করতে হবে।
অ্যালগরিদম (Two-Pointer Approach)
- দুটি পয়েন্টার: low (শুরু) এবং high (শেষ)।
- স্ট্রিং a-র low এবং b-র high চেরেক্টার তুলনা করুন।
- যতক্ষণ সমান, ততক্ষণ low++, high--।
- যখন ভিন্ন হয়, তখন a[low...high] বা b[low...high] যেকোনো একটি প্যালিনড্রোম কিনা চেক করুন।
- স্ট্রিং বদলিয়ে (Split(b, a))ও চেক করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string &s, int l, int r) {
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
bool checkSplit(string &a, string &b) {
int low = 0, high = a.size() - 1;
while (low < high && a[low] == b[high]) {
low++; high--;
}
return isPalindrome(a, low, high) || isPalindrome(b, low, high);
}
bool checkPalindromic(string a, string b) {
if (a.size() < 2) return true;
return checkSplit(a, b) || checkSplit(b, a);
}
int main() {
string a = "abcpqr", b = "mnocba";
cout << (checkPalindromic(a, b) ? "True" : "False") << endl;
return 0;
}
আউটপুট
True
ইনডেক্স ২-এ স্প্লিট করলে: "abc" + "cba" = "abccba" (প্যালিনড্রোম)।
