Make String Anti-Palindrome – GeeksforGeeks

By Ann Roberts On Dec 23, 2022

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given a string S of length N is said to be an Anti-palindrome string if, for each 0 ≤ i ≤ N-1, S_i != S_{(N – 1 − i)}. The task is to print Anti-Palindrome String formed, If it is not possible to find print “-1”

Examples:

Input: S = “abdcccdb”
Output: “cbbaccdd”
Explanation: cbbaccdd is an Anti-palindrome string as for each 0 ≤ i ≤ N-1, Si != S(N-1−i).

Input: s = “xyz”
Output: -1

Approach: The problem can be solved based on the following idea:

If the length of the string S is odd, Then the answer is always “-1” as the condition fails on the middle element. Count the frequency of each character in the string S, if any character frequency is more than half the length of the string, then also the condition fails. Otherwise, print the string having characters continuously up to their respective frequencies.

Follow the below steps to implement the idea:

Check the length of the string, If it is odd print “-1“.
Else, count the frequency of each character using the map.
If any character frequency is more than half of the string S length, print “-1”.
Else, print the string having characters continuously up to their respective frequencies.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

string checkPalindrome(string s)

{

int n = s.size();

if (n & 1) {

return "-1";

}

map<char, int> Mp;

for (int i = 0; i < n; i++)

Mp[s[i]]++;

string r = "";

for (auto i : Mp) {

int p = i.second;

if (p > (n / 2)) {

return "-1";

}

for (int j = 0; j < p; j++) {

r += i.first;

}

reverse(r.begin(), r.begin() + n / 2);

return r;

}

int main()

{

string s = "abdcccdb";

cout << checkPalindrome(s) << endl;

return 0;

}

Time Complexity: O(N * log N)
Auxiliary Space: O(N)

Related Articles:

Improve Article

Save Article

Like Article

Improve Article

Save Article

Examples:

Input: S = “abdcccdb”
Output: “cbbaccdd”
Explanation: cbbaccdd is an Anti-palindrome string as for each 0 ≤ i ≤ N-1, Si != S(N-1−i).

Input: s = “xyz”
Output: -1

Approach: The problem can be solved based on the following idea:

If the length of the string S is odd, Then the answer is always “-1” as the condition fails on the middle element. Count the frequency of each character in the string S, if any character frequency is more than half the length of the string, then also the condition fails. Otherwise, print the string having characters continuously up to their respective frequencies.

Follow the below steps to implement the idea:

Check the length of the string, If it is odd print “-1“.
Else, count the frequency of each character using the map.
If any character frequency is more than half of the string S length, print “-1”.
Else, print the string having characters continuously up to their respective frequencies.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

string checkPalindrome(string s)

{

int n = s.size();

if (n & 1) {

return "-1";

}

map<char, int> Mp;

for (int i = 0; i < n; i++)

Mp[s[i]]++;

string r = "";

for (auto i : Mp) {

int p = i.second;

if (p > (n / 2)) {

return "-1";

}

for (int j = 0; j < p; j++) {

r += i.first;

}

reverse(r.begin(), r.begin() + n / 2);

return r;

}

int main()

{

string s = "abdcccdb";

cout << checkPalindrome(s) << endl;

return 0;

}

Time Complexity: O(N * log N)
Auxiliary Space: O(N)

Related Articles:

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.