Check rearranged string can form a palindrome


StringViews 4296

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"; 
    }
}

Try It

 

Translate »