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;
}
};