मान लीजिए हमारे पास एक पैलिंड्रोमिक स्ट्रिंग palindrome है, हमें इसमें ठीक एक अक्षर को किसी भी लोअरकेस अंग्रेजी अक्षर से बदलना है ताकि स्ट्रिंग लेक्सिकोग्राफिक रूप से सबसे छोटी संभव स्ट्रिंग बन जाए जो पैलिंड्रोम न हो। ऐसा करने के बाद हमें अंतिम स्ट्रिंग ढूंढनी है। यदि ऐसा करना संभव न हो, तो खाली स्ट्रिंग वापस करें। उदाहरण के लिए, यदि इनपुट "abccba" है, तो आउटपुट "aaccba" होगा।
समाधान दृष्टिकोण
changedको false सेट करें।- यदि स्ट्रिंग का आकार 1 है, तो खाली स्ट्रिंग वापस करें।
- i = 0 और j = स्ट्रिंग की लंबाई - 1 सेट करें।
leftAऔरrightAको true सेट करें।- जब तक i < j हो:
- यदि s[i] 'a' नहीं है, तो s[i] को 'a' बनाएं और स्ट्रिंग वापस करें।
- i को 1 बढ़ाएं और j को 1 घटाएं।
- अंतिम अक्षर को 'b' बनाएं।
- स्ट्रिंग वापस करें।
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;
}
};
int main() {
Solution ob;
cout << (ob.breakPalindrome("abccba"));
return 0;
}
इनपुट
"abccba"
आउटपुट
aaccba
