# Make A String Anti-Palindrome in Java

Given a string S of length N has a property known as Si! = S(N – 1? i) for every 0? i?? N-1, then the string is considered anti-palindrome. Our task is to create the anti-palindrome. In an instance that it cannot be situated, return "-1."

Example 1:

Input:

`String str = "abccda"`

Output:

`The anti-palindrome string is baaccd`

Explanation:

The string baaccd is an anti-palindrome for the given string since Si!= S(N-1?i) for every 0? i? N-1.

Example 2:

Input:

`String str = "abc"`

Output:

`-1`

Explanation:

No palindrome exists for the given string.

Example 3:

Input:

`String str = "aaaaa"`

Output:

`-1`

Explanation:

No palindrome exists for the given string.

## Approach: Naïve Approach

If the string Str has an odd length, the condition fails on the middle element; hence, the answer is always "-1." Once we have determined how frequently each character appears in the string S, we may check if the condition also fails if the character frequency exceeds half the string's length. In the instance that is not executed, print the string continually with the characters up to the required frequencies.

### Algorithm:

Step 1: Check the length of the string and display "-1" if it is unusual.

Step 2: Analyse the map to determine the frequency of each character if not.

Step 3: Print "-1" if the frequency of any character exceeds half of the length of the string S.

Step 4: If not, print the string with characters appearing consistently up to the appropriate frequencies.

## Implementation:

FileName: AntiPalindrome.java

`import java.io.*;import java.util.*;public class AntiPalindrome{            // Function to determine whether or not the string            // is a palindrome            public static String checkPalindrome(String str)            {                        int n = str.length();                        if (n % 2 == 1)                        {                                    return "-1";                        }                        // Declaration of a Map                        Map<Character, Integer> Map = new HashMap<>();                        // Counting the frequency of occurence of each element                        for (int i = 0; i < n; i++)                        {                                    Map.put(str.charAt(i),                                                Map.getOrDefault(str.charAt(i), 0) + 1);                        }                        String res = "";                        // Traversal of the Map                        for (Map.Entry<Character, Integer> entry : Map.entrySet())                        {                                    int palin = entry.getValue();            // It is impossible to create            // an anti-palindrome if the maximum            // frequency of any character is more than n/2.                                    if (palin > (n / 2))                                    {                                                return "-1";                                    }                                    // Otherwise, create a non-palindrome string.                                    for (int j = 0; j < palin; j++)                                    {                                                res += entry.getKey();                                    }                        }                        // reverse of the string                        res = new StringBuilder(res.substring(0, n / 2)) .reverse() .toString() + res.substring(n / 2);                        // return of the string                        return res;            }            public static void main(String[] args)            {                        String str = "abccda";                        System.out.println("The anti-palindrome of the given string is " + checkPalindrome(str));            }}`

Output:

`The anti-palindrome of the given string is baaccd`

Complexity Analysis:

The above code's time complexity is O(N * log N), and its Space Complexity is O(N), where N represents the length of the given string.