Make String Anti-Palindrome – GeeksforGeeks

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++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to check whether the string
// can be palindrome or not
string checkPalindrome(string s)
{

    // Size of string
    int n = s.size();

    // If n is odd it is impossible to make
    if (n & 1) {
        return "-1";
    }

    // Declare a Map
    map<char, int> Mp;

    // Count the frequency of each element
    for (int i = 0; i < n; i++)

        Mp[s[i]]++;

    string r = "";

    // Traverse the Map
    for (auto i : Mp) {

        int p = i.second;

        // If max frequency of any character
        // is greater than n/2 then it is
        // impossible to make Anti-palindrome
        if (p > (n / 2)) {
            return "-1";
        }

        // Else make the non-palindrome string
        for (int j = 0; j < p; j++) {

            r += i.first;
        }
    }

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

    // return the string
    return r;
}

// Driver Code
int main()
{
    string s = "abdcccdb";

    // Function call
    cout << checkPalindrome(s) << endl;

    return 0;
}

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

Related Articles: