ধরুন আমাদের একটি প্যালিনড্রোমিক স্ট্রিং প্যালিনড্রোম আছে, আমাদেরকে যেকোন ছোট হাতের ইংরেজি অক্ষর দ্বারা ঠিক একটি অক্ষর প্রতিস্থাপন করতে হবে যাতে স্ট্রিংটি আভিধানিকভাবে সবচেয়ে ছোট সম্ভাব্য স্ট্রিং হয়ে যায় যা প্যালিনড্রোম নয়। এখন এটি করার পরে, আমাদের চূড়ান্ত স্ট্রিংটি খুঁজে বের করতে হবে। যদি এটি করার কোন উপায় না থাকে, তাহলে খালি স্ট্রিংটি ফেরত দিন। তাই ইনপুট যদি "abccba" এর মত হয়, তাহলে আউটপুট হবে "aaccba"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
পরিবর্তিত :=মিথ্যা
-
যদি একটি স্ট্রিংয়ের আকার 1 হয়, তাহলে একটি ফাঁকা স্ট্রিং ফেরত দিন
-
i :=0 এবং j :=s – 1
এর দৈর্ঘ্য -
leftA :=True এবং rightA :=True
-
যখন আমি
-
যদি s[i] 'a' না হয়, তাহলে s[i] কে 'a' হিসেবে সেট করুন এবং s ফেরত দিন
-
i 1 দ্বারা বাড়ান এবং j 1 দ্বারা কমান
-
-
s[s - 1 এর আকার] :=‘b’
-
s
ফেরত দিন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string breakPalindrome(string s) {
bool changed = false;
if(s.size() == 1)return "";
int i = 0, j = s.size() - 1;
bool leftA = true;
bool rightA= true;
while(i < j){
if(s[i] != 'a'){
s[i] = 'a';
return s;
}
i++;
j--;
}
s[s.size() - 1] = 'b';
return s;
}
};
main(){
Solution ob;
cout << (ob.breakPalindrome("abccba"));
} ইনপুট
"abccba"
আউটপুট
aaccba
