1
class Solution {
2
 public:
3
  string reorganizeString(string s) {
4
    // Step1: insert elements to the map so that we will get the frequency
5
    unordered_map<char, int> mp;
6
    for (auto i : s) {
7
      mp[i]++;
8
    }
9

10
    // Step2: Create a max heap to store all the elements according to there
11
    // frequency
12
    priority_queue<pair<int, char>> pq;
13

14
    for (auto it : mp) {
15
      pq.push({it.second, it.first});
16
    }
17

18
    // Step3: Now take two elements from the heap and do this till the map
19
    // becomes size 1
20
    //  why one : cause we are taking two top elements like pq.top is a then
21
    //  will pop and again pq.top is b and will add to answer
22
    string ans = "";
23
    while (mp.size() > 1) {
24
      // get the top two elements from heap
25
      char ch1 = pq.top().second;
26
      ans += ch1;
27
      pq.pop();
28
      char ch2 = pq.top().second;
29
      ans += ch2;
30
      pq.pop();
31

32
      // now reduce the size in the mp
33
      //  now we have added two char in the ans so reduce the cound in map
34
      mp[ch1]--;
35
      mp[ch2]--;
36

37
      // Now check if it's size is still greater than 0 then push
38
      //  if size is greater in map than 0 then we again need to push into the
39
      //  map so that we can make the ans string
40
      if (mp[ch1] > 0) {
41
        pq.push({mp[ch1], ch1});
42
      } else {
43
        // if the size is 0 then decrese the map means erase the map
44
        mp.erase(ch1);
45
      }
46
      if (mp[ch2] > 0) {
47
        pq.push({mp[ch2], ch2});
48
      } else {
49
        mp.erase(ch2);
50
      }
51
    }
52

53
    // Step4 : Now check wheather any element is present into it
54
    //  Now we have zero size of the map so check top element size is greater
55
    //  than 1 or not if greater the we cannot split it since it''s only that
56
    //  char if not add to ans
57
    if (mp.size() == 1) {
58
      if (mp[pq.top().second] > 1) {
59
        return "";
60
      }
61
      ans += pq.top().second;
62
    }
63
    // returrn ans
64
    return ans;
65
  }
66
};