Table of Contents
Check if the input string can be rearranged such that it can be a palindrome.
Example
Input string : “abb”
Output : True
Because, it can be rearranged as “bab” which is palindrome.
Time complexity : O(n)
Algorithm
a. Create a count array, store the count of all the characters.
1. Create count array with size of ascii values.
2. Initialize it with zeroes.
3. Traverse the string and update the count array.
b. If count of characters array has odd count more than once return True.
c. Else, False.
C++ Program
#include <iostream>
using namespace std;
#define ASCII_VALUES 256
//Main function
int main()
{
const char *str = "abb";
//Initialize with zeroes
int count[ASCII_VALUES] = {0};
//update count array with count of charcters in the input string
for (int i = 0; str[i]; i++)
{
count[str[i]]++;
}
//count odd numbers count in the count array
int odd_count = 0;
for (int i = 0; i < ASCII_VALUES; i++)
{
if (count[i] & 1)
{
odd_count++;
}
}
if (odd_count > 1)//If odd count is > 1 return false
{
cout<<"given string cannot be rearranged to form a palindrome";
}
else//return true if count < 1
{
cout<<"given string can be rearranged to form a palindrome";
}
}