Check rearranged string can form a palindrome


Check if the input string can be rearranged such that it can be a palindrome.


Input string : “abb”
Output : True

Because, it can be rearranged as “bab” which is palindrome.

Time complexity : O(n)


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 odd numbers count in the count array
    int odd_count = 0;
    for (int i = 0; i < ASCII_VALUES; i++)
        if (count[i] & 1)
    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


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup