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 MapMap = 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 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.