Check rearranged string can form a palindrome  


String

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.

Please click Like if you loved this article?

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

 

Please click Like if you loved this article?

See also
String startswith() and endswith()
Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh