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

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

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

Here is simple and easy solution using unordered_map with execution time is 0.07s.

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	     string s;
	     cin>>s;
	     unordered_map<char,int> mp;
	     int mx=0;
	     
	     for(int i=0;i<s.size();++i)
	     {
	          mp[s[i]]++;
	         if(mx<mp[s[i]])
	          mx=mp[s[i]];
	     }
	     
	     if((s.size()>3&&mx>s.size()/2)||(s.size()>=2&&mp.size()==1))
	     cout<<0<<endl;
	     else
	     cout<<1<<endl;
	     
	}
	return 0;
}