Answers for "Reorganize String"

C++
0

Reorganize String

#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<queue>
using namespace std;
class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> um;
        priority_queue<pair<int, char>> pq;
        string output = "";

        for (auto i : s)
            um[i]++;

        for (auto &i : um)
            pq.push({i.second, i.first});

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

            output += top1.second;
            output += top2.second;

            if (--top1.first > 0){
                pq.push(top1);
            }
            if (--top2.first > 0){
                pq.push(top2);
            }
        }

        if (pq.size()) {
            if (pq.top().first == 1)
                output += pq.top().second;
            else
                return "";
        }
        return output;
    }
};
int main(){
  string s = "aaaaaccbbb";
  Solution o;
  cout<<o.reorganizeString(s);
}

# ./a.out
abacabacba
Posted by: Guest on April-27-2021

Browse Popular Code Answers by Language