Rearrange characters in a string such that no two adjacent are same

Given a string with repeated characters, the task is to rearrange characters in a string so that no two adjacent characters are same.

Note: It may be assumed that the string has only lowercase English alphabets.

Examples:

Input: aaabc 
Output: abaca 

Input: aaabb
Output: ababa 

Input: aa 
Output: Not Possible

Input: aaaabc 
Output: Not Possible

Asked In: Amazon Interview, Adobe

// C++ program to rearrange characters in a string

// so that no two adjacent characters are same.

#include

using namespace std;

const int MAX_CHAR = 26;

typedef pair kv;

// Function to rearrange character of a string

// so that no char repeat twice

void rearrangeString(string str)

{

int n = str.length();

// Store frequencies of all characters in string

int count[MAX_CHAR] = {0};

for (int i = 0 ; i < n ; i++)

count[str[i]-'a']++;

// Insert all characters with their frequencies

// into a priority_queue

priority_queue< kv > pq;

for (char c = 'a' ; c <= 'z' ; c++)

if (count[c-'a'])

pq.push( kv(count[c-'a'], c));

// 'str' that will store resultant value

str = "" ;

// work as the previous visited element

// initial previous element be. ( '#' and

// it's frequency '-1' )

kv prev (-1, '#') ;

// traverse queue

while (!pq.empty())

{

// pop top element from queue and add it

// to string.

kv k = pq.top();

pq.pop();

str = str + k.second;

// IF frequency of previous character is less

// than zero that means it is useless, we

// need not to push it

if (prev.first > 0)

pq.push(prev);

// make current character as the previous 'char'

// decrease frequency by 'one'

(k.first)--;

         prev =  k;

}

// If length of the resultant string and original

// string is not same then string is not valid

if (n != str.length())

cout << " Not valid String " << endl;

else // valid string

cout << str << endl;

}

// Driver program to test above function

int main()

{

string str = "bbbaa" ;

rearrangeString(str);

return 0;

}