Given a string S of length N is said to be an Anti-palindrome string if, for each 0 ? i ? N-1, Si != 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++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether the string// can be palindrome or notstring 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 Codeint main(){ string s = "abdcccdb"; // Function call cout << checkPalindrome(s) << endl; return 0;} |
Java
// Java implementation for the above approachimport java.io.*;import java.util.*;class GFG { // Function to check whether the string // can be palindrome or not public static String checkPalindrome(String s) { // Size of string int n = s.length(); // If n is odd it is impossible to make if (n % 2 == 1) { return "-1"; } // Declare a Map Map<Character, Integer> Mp = new HashMap<>(); // Count the frequency of each element for (int i = 0; i < n; i++) { Mp.put(s.charAt(i), Mp.getOrDefault(s.charAt(i), 0) + 1); } String r = ""; // Traverse the Map for (Map.Entry<Character, Integer> entry : Mp.entrySet()) { int p = entry.getValue(); // 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 += entry.getKey(); } } // reverse the string r = new StringBuilder(r.substring(0, n / 2)) .reverse() .toString() + r.substring(n / 2); // return the string return r; } public static void main(String[] args) { String s = "abdcccdb"; // Function call System.out.println(checkPalindrome(s)); }}// This code is contributed by lokesh. |
Python3
def reverse(s): str = "" for i in s: str = i + str return strdef checkPalindrome(s): # Size of string n = len(s) # If n is odd it is impossible to make if n & 1 != 0: return "-1" # Declare an object frequency = dict() # Count the frequency of each element for item in s: if (item in frequency): frequency[item] += 1 else: frequency[item] = 1 r = ""; # Traverse the object for i in frequency: p = frequency[i] # 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 j in range(p): r += i # reverse the string print(reverse(r))checkPalindrome("abdcccdb")# The code is contributed by Gautam goel. |
Javascript
function checkPalindrome(s) { // Size of string let n = s.length; // If n is odd it is impossible to make if (n & 1) { return "-1"; } // Declare an object let frequency = {}; // Count the frequency of each element for (let i = 0; i < n; i++) { if (frequency[s[i]]) { frequency[s[i]]++; } else { frequency[s[i]] = 1; } } let r = ""; // Traverse the object for (let i in frequency) { let p = frequency[i]; // 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 (let j = 0; j < p; j++) { r += i; } } // reverse the string r = r.split('').reverse().join(''); // return the string return r;}console.log(checkPalindrome("abdcccdb")); |
C#
using System;using System.Collections.Generic;class GFG { // Function to check whether the string // can be palindrome or not public static string CheckPalindrome(string s) { // Size of string int n = s.Length; // If n is odd it is impossible to make if (n % 2 == 1) { return "-1"; } // Declare a dictionary Dictionary<char, int> Mp = new Dictionary<char, int>(); // Count the frequency of each element for (int i = 0; i < n; i++) { if (!Mp.ContainsKey(s[i])) { Mp.Add(s[i], 1); } else { Mp[s[i]]++; } } string r = ""; // Traverse the dictionary foreach(KeyValuePair<char, int> entry in Mp) { int p = entry.Value; // 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 += entry.Key; } } // reverse the string char[] charArray = r.Substring(0, n / 2).ToCharArray(); Array.Reverse(charArray); r = new string(charArray) + r.Substring(n / 2); // return the string return r; } static void Main(string[] args) { string s = "abdcccdb"; // Function call Console.WriteLine(CheckPalindrome(s)); }} // this code is contributed by writer |
Output
cbbaccdd
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
