RearrangeCharecters.cpp

// Rearrange characters 

// Given a string S with repeated characters. The task is to rearrange characters in a string such 
// that no two adjacent characters are the same. 

// Note: The string has only lowercase English alphabets and it can have multiple solutions. Return any one of them.

// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;

 // } Driver Code Ends
class Solution
{
    public:
    struct Key{
    	int freq; // store frequency of character
    	char ch;
    	bool operator<(const Key &k) const
    	{
    		return freq < k.freq;
    	}
    };
    public:
    string rearrangeString(string str)
    {
        //code here
        int n = str.length();
    	int count[26] = {0};
    	for (int i = 0 ; i < n ; i++)
    		count[str[i]-'a']++;
    	priority_queue< Key > pq;
    	for (char c = 'a' ; c <= 'z' ; c++)
    		if (count[c-'a'])
    			pq.push( Key { count[c-'a'], c} );
    	str = "" ;
    	Key prev {-1, '#'} ;
    	while (!pq.empty())
    	{
    		Key k = pq.top();
    		pq.pop();
    		str = str + k.ch;
    		if (prev.freq > 0)
    			pq.push(prev);
    		(k.freq)--;
    		prev = k;
    	}
    	if (n != str.length())
    		return "-1";
    	else
    		return str;
    }
    
};

// { Driver Code Starts.
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
	    string str;
	    cin>>str;
	    Solution ob;
	    string str1=ob.rearrangeString(str);
	    int flag=1;
	    int c[26] = {0};
	    for(int i=0; i<str.length(); i++)
	        c[str[i]-'a']+=1;
	    int f = 0;
	    int x = (str.length()+1)/2;
	    for(int i=0; i<26; i++)
	    {
	        if(c[i]>x)
	            f = 1;
	    }
	    if(f)
	    {
	        if(str1=="-1")
	            cout<<0<<endl;
	        else
	            cout<<1<<endl;
	    }
	    else
	    {
    	    int a[26] = {0};
    	    int b[26] = {0};
    	    for(int i=0; i<str.length(); i++)
    	        a[str[i]-'a']+=1;
    	    for(int i=0; i<str1.length(); i++)
    	        b[str1[i]-'a']+=1;
    	        
    	    for(int i=0; i<26; i++)
    	        if(a[i]!=b[i])
    	            flag = 0;
    	    
    	    for(int i=0;i<str1.length();i++)
    	    {
    		    if(i>0)
    		        if(str1[i-1]==str1[i])
    			        flag=0;
    	    }
    	    if(flag==1)
    		    cout<<"1\n";
    	    else
    	        cout<<"0\n";
	    }
	}
    return 0;
}  // } Driver Code Ends