Strings: Check if it is possible to re-arrange characters in a string, such a way that no two adjacent are same

Problem Statement:

You are given a string, you need to check if ti is possible to rearrange the string such that no two adjacent characters are same.

Example

Input: aab
Output: Yes

Why?
You can swap the string to “aba”. So no 2 adjacent characters are same.

Solution

The solution is very simple.
We need to get the character that has max repeat frequency.
Let it be max.
Then we check if max <= n-max+1, where n is the length of the string.
If it satisfies this condition, then return 1.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>

using namespace std;

int check_if_possible(string str) 
{ 
  
    // to store the frequency of each character
    unordered_map<char, int> freq; 
  
    int max_freq = 0;  

    for (int j = 0; j < (str.length()); j++) 
    {
        freq[str[j]]++; 
        if (freq[str[j]] > max_freq)
        {
            max_freq = freq[str[j]]; 
        }
    } 
  
    
    if (max_freq <= (str.length() - max_freq + 1)) 
        return true; 
    return false; 
} 
  
// Driver code 
int main() 
{ 
    string str = "aab"; 
  
    if (check_if_possible(str)) 
        cout << "1"; 
    else
        cout << "0"; 
  
    return 0; 
} 

Output:

1