Reorganize String Problem

Description

LeetCode Problem 767.

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return “” if not possible.

Example 1:

``````1
2
Input: s = "aab"
Output: "aba"
``````

Example 2:

``````1
2
Input: s = "aaab"
Output: ""
``````

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Sample C++ Code using Priority Queue

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
string reorganizeString(string S) {
string res = "";
unordered_map<char,int> mp;
priority_queue<pair<int,char>> pq;

for (auto s : S)
mp[s] += 1;
for (auto m : mp)
pq.push(make_pair(m.second, m.first));

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

res += top1.second;
res += top2.second;

top1.first -= 1;
top2.first -= 1;

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

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

return res;
}
};
``````