Table of Contents
Problem Statement
The problem “Palindrome Permutation” states that you are given a string. Check if it can be rearranged to form a palindromic string.
Example
superdupers
yes
Explanation
The given input string can be rearranged to superdrepus. It is a palindromic string. So our answer to this example is yes.
Approach
If all the characters occur even number of times and at most one character occurs the odd number of times then the string can be converted into a palindromic string.
To implement this approach we maintain a count array of size 128 and initialize with zero. Iterate through the string and increase the count of each character encountered in an array. Now iterate through the array and if at most one character occurs the odd number of times then return true else return false.
Code
C++ code for Palindrome Permutation
// C++ implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
#include<bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
/* function to check whether characters of a string can form
a palindrome */
bool canFormPalindrome(string str)
{
// Create a count array and initialize all
// values as 0
int count[NO_OF_CHARS] = {0};
// For each character in input strings,
// increment count in the corresponding
// count array
for (int i = 0; str[i]; i++)
count[str[i]]++;
// Count odd occurring characters
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++)
{
if (count[i] & 1)
odd++;
if (odd > 1)
return false;
}
// Return true if odd count is 0 or 1,
return true;
}
/* Driver program*/
int main()
{
canFormPalindrome("superdupers")? cout << "Yes\n":
cout << "No\n";
return 0;
}Yes
Java code for Palindrome Permutation
// Java implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
import java.io.*;
import java.util.*;
import java.math.*;
class check {
static int NO_OF_CHARS = 256;
/* function to check whether characters
of a string can form a palindrome */
static boolean canFormPalindrome(String str) {
// Create a count array and initialize all
// values as 0
int count[] = new int[NO_OF_CHARS];
Arrays.fill(count, 0);
// For each character in input strings,
// increment count in the corresponding
// count array
for (int i = 0; i < str.length(); i++)
count[(int)(str.charAt(i))]++;
// Count odd occurring characters
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++)
{
if ((count[i] & 1) == 1)
odd++;
if (odd > 1)
return false;
}
// Return true if odd count is 0 or 1,
return true;
}
// Driver program
public static void main(String args[])
{
if (canFormPalindrome("superdupers"))
System.out.println("Yes");
else
System.out.println("No");
}
}Yes
Complexity Analysis
Time complexity
O(n) because we are traversing the array only once to check if the given string can be converted to a palindromic string. So the time complexity becomes O(n).
Space complexity
The space complexity for the program to check if the given string can be converted to a palindromic string is O(1) because we are using an array of size 128 to store the frequency of each character.
Efficient Approach
In this approach, we will maintain a list. Then we will iterate through the string and if the character is already present in the list we remove it else we insert that character into the list. After iteration, if the number of elements in the list is greater than one. So, it can’t be converted into a palindromic string.
Code
Optimized C++ code for Palindrome Permutation
#include<bits/stdc++.h>
using namespace std;
/*
* function to check whether characters of
a string can form a palindrome
*/
bool canFormPalindrome(string str)
{
// Create a list
vector<char> list;
// For each character in input strings,
// remove character if list contains
// else add character to list
for (int i = 0; i < str.length(); i++)
{
auto pos = find(list.begin(), list.end(), str[i]);
if (pos != list.end())
{
auto posi = find(list.begin(), list.end(),str[i]);
list.erase(posi);
}
else
list.push_back(str[i]);
}
// if character length is even list is expected to be empty
// or if character length is odd list size is expected to be 1
if (str.length() % 2 == 0 && list.empty() // if string length is even
|| (str.length() % 2 == 1 && list.size() == 1)) // if string length is odd
return true;
else
return false;
}
// Driver program
int main()
{
if (canFormPalindrome("superdupers"))
cout << ("Yes") << endl;
else
cout << ("No") << endl;
}Yes
Optimized Java code for Palindrome Permutation
import java.util.ArrayList;
import java.util.List;
class check{
/*
* function to check whether characters of a string can form a palindrome
*/
static boolean canFormPalindrome(String str) {
// Create a list
List<Character> list = new ArrayList<Character>();
// For each character in input strings,
// remove character if list contains
// else add character to list
for (int i = 0; i < str.length(); i++) {
if (list.contains(str.charAt(i)))
list.remove((Character) str.charAt(i));
else
list.add(str.charAt(i));
}
// if character length is even list is expected to be empty
// or if character length is odd list size is expected to be 1
if (str.length() % 2 == 0 && list.isEmpty() // if string length is even
|| (str.length() % 2 == 1 && list.size() == 1)) // if string length is odd
return true;
else
return false;
}
// Driver program
public static void main(String args[]) {
if (canFormPalindrome("superdupers"))
System.out.println("Yes");
else
System.out.println("No");
}
}Yes
Complexity Analysis
Time complexity
O(n) because we are traversing the array only once to check if the given string can be converted to a palindromic string. So the time complexity becomes O(n).
Space complexity
The space complexity for the program to check if the given string can be converted to a palindromic string is O(1).