## Approach 1: Heap

• Time:O(n\log 26) = O(n)
• Space:O(n)

## C++

``````class Solution {
public:
string reorganizeString(string s) {
unordered_map<char, int> count;
int maxFreq = 0;

for (const char c : s)
maxFreq = max(maxFreq, ++count[c]);

if (maxFreq > (s.length() + 1) / 2)
return "";

string ans;
priority_queue<pair<int, char>> maxHeap;  // (freq, c)
int prevFreq = 0;
char prevChar = '@';

for (const auto& [c, freq] : count)
maxHeap.emplace(freq, c);

while (!maxHeap.empty()) {
// get the most freq letter
const auto [freq, c] = maxHeap.top();
maxHeap.pop();
ans += c;
// add the previous letter back so that
// any two adjacent characters are not the same
if (prevFreq > 0)
maxHeap.emplace(prevFreq, prevChar);
prevFreq = freq - 1;
prevChar = c;
}

return ans;
}
};
``````

## JAVA

``````public class Solution {
public String reorganizeString(String s) {
Map<Character, Integer> count = new HashMap<>();
int maxFreq = 0;

for (final char c : s.toCharArray()) {
count.merge(c, 1, Integer::sum);
maxFreq = Math.max(maxFreq, count.get(c));
}

if (maxFreq > (s.length() + 1) / 2)
return "";

StringBuilder sb = new StringBuilder();
// (freq, c)
Queue<Pair<Integer, Character>> maxHeap =
new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
int prevFreq = 0;
char prevChar = '@';

for (final char c : count.keySet())
maxHeap.offer(new Pair<>(count.get(c), c));

while (!maxHeap.isEmpty()) {
// get the most freq letter
final int freq = maxHeap.peek().getKey();
final char c = maxHeap.poll().getValue();
sb.append(c);
// add the previous letter back so that
// any two adjacent characters are not the same
if (prevFreq > 0)
maxHeap.offer(new Pair<>(prevFreq, prevChar));
prevFreq = freq - 1;
prevChar = c;
}

return sb.toString();
}
}
``````

## Python

``````class Solution:
def reorganizeString(self, s: str) -> str:
count = Counter(s)
if max(count.values()) > (len(s) + 1) // 2:
return ''

ans = []
maxHeap = [(-freq, c) for c, freq in count.items()]
heapq.heapify(maxHeap)
prevFreq = 0
prevChar = '@'

while maxHeap:
# get the most freq letter
freq, c = heapq.heappop(maxHeap)
ans.append(c)
# add the previous letter back so that
# any two adjacent characters are not the same
if prevFreq < 0:
heapq.heappush(maxHeap, (prevFreq, prevChar))
prevFreq = freq + 1
prevChar = c

return ''.join(ans)
``````

• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
string reorganizeString(string s) {
const int n = s.length();
vector<int> count(128);
char maxChar = 'a' - 1;

for (const char c : s)
++count[c];

for (char c = 'a'; c <= 'z'; ++c)
if (count[c] > count[maxChar])
maxChar = c;

if (count[maxChar] > (n + 1) / 2)
return "";

string ans(n, ' ');
int i = 0;  // ans's index

auto fillIn = [&](char c) {
ans[i] = c;
i += 2;
if (i >= n)  // out of bound, reset the index to 1
i = 1;
};

// fill in 0, 2, 4, ... indices with the maxCount char
while (count[maxChar]-- > 0)
fillIn(maxChar);

// fill in remaining characters
for (char c = 'a'; c <= 'z'; ++c)
while (count[c] > 0) {
--count[c];
fillIn(c);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public String reorganizeString(String s) {
final int n = s.length();

int[] count = new int[128];
char maxChar = 'a' - 1;

for (final char c : s.toCharArray())
++count[c];

for (char c = 'a'; c <= 'z'; ++c)
if (count[c] > count[maxChar])
maxChar = c;

if (count[maxChar] > (n + 1) / 2)
return "";

char[] ans = new char[n];

// fill in 0, 2, 4, ... indices with the maxCount char
while (count[maxChar]-- > 0)
fillIn(ans, maxChar);

// fill in remaining characters
for (char c = 'a'; c <= 'z'; ++c)
while (count[c] > 0) {
--count[c];
fillIn(ans, c);
}

return new String(ans);
}

private int i = 0; // ans's index

private void fillIn(char[] ans, char c) {
ans[i] = c;
i += 2;
if (i >= ans.length) // out of bound, reset the index to 1
i = 1;
}
}
``````

## Python

``````class Solution:
def reorganizeString(self, s: str) -> str:
n = len(s)
count = Counter(s)
maxCount = max(count.values())

if maxCount > (n + 1) // 2:
return ''

if maxCount == (n + 1) // 2:
maxLetter = max(count, key=count.get)
ans = [maxLetter if i % 2 == 0 else '' for i in range(n)]
del count[maxLetter]
i = 1
else:
ans = [''] * n
i = 0

for c, freq in count.items():
for _ in range(freq):
ans[i] = c
i += 2
if i >= n:
i = 1

return ''.join(ans)
``````