767. Reorganize String
Description
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 <= 500s consists of lowercase English letters.
Hints/Notes
Solution
Language: C++
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
| class Solution {
public:
string reorganizeString(string s) {
map<char, int> m;
for (char& c : s) {
m[c]++;
}
priority_queue<pair<int,char>> pq;
for (auto& [k, v] : m) {
pq.emplace(v, k);
}
string res;
while (!pq.empty()) {
auto [freq1, c1] = pq.top();
pq.pop();
res.push_back(c1);
freq1--;
if (pq.empty()) {
if (freq1 > 0) {
return "";
} else {
return res;
}
}
auto [freq2, c2] = pq.top();
pq.pop();
res.push_back(c2);
freq2--;
if (freq1) pq.emplace(freq1, c1);
if (freq2) pq.emplace(freq2, c2);
}
return res;
}
};
|