Greedy: Reorganize String

Problem Statement:

You are given a string, you need to re-arrange the staring such that no two adjacent characters are not the same.

Example:

Input: s = 'aab'

Output: s = 'aba'

Solution Explanation:

We will solve the problem with greedy approach.

Get the frequency of each letter.

We always try to place the highest frequency character so to complete it quickly.

Extract 2 most frequency character and append to the result.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;


string solution(string s) 
{
    if (s.size() == 1)
    {
        return s;
    }
    else if (s.size() == 0){

        return "";
    }

    unordered_map <char , int> mp;
    for (auto it : s)
    {
        mp[it]++;
    }

    string result = "";

    priority_queue <pair <int , char>> pq;
    for (auto it : mp)
    {
        pq.push({it.second , it.first}); // {frequency , character}
    }

    while (pq.size() > 1)
    {
       auto it = pq.top();
       pq.pop();

       auto it1 = pq.top();
       pq.pop();

       result += it.second;
       it.first--;

       result += it1.second;
       it1.first--;

       if (it.first > 0)
       {
           pq.push(it);
       }
       if (it1.first > 0)
       {
           pq.push(it1);
       }

    }
    
    if (!pq.empty()) 
    {
        if (pq.top().first > 1) 
        {
            return ""; 
        }
        result += pq.top().second;
    }
    return result;
}


int main() 
{
    string s = "aaabc";
    cout << solution(s);
    return 0;
}

Output

acaba