## Algorithm

Problem Name: 767. Reorganize String

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:

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

Example 2:

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

Constraints:

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
char c;
int n;
} e_t;
int cmp(const void *a, const void *b) {
e_t *p1 = a;
e_t *p2 = b;
return (p1->n  <  p2->n) ? 1 :
(p1->n > p2->n) ? -1 : 0;
}
char * reorganizeString(char * S){
e_t e[27] = { 0 }, x;
char c, *p, *buff;
int i, t, sz;

buff = malloc(501);
//assert(buff);
buff[0] = 0;

while (c = *(S ++)) {
i = c - 'a';
e[i].c = c;
e[i].n ++;
}

qsort(&e, 26, sizeof(e_t), cmp);

for (i = 25; i >= 0; i --) if (e[i].n > 0) break;

sz = i + 1;

p = buff;
*p = 0;

while (e[0].n > 0) {
*p = e[0].c;
p ++;
e[0].n --;

if (e[1].n > 0) {
*p = e[1].c;
p ++;
e[1].n --;
} else if (e[0].n > 0) {
buff[0] = 0;
break;
}

qsort(&e, sz, sizeof(e_t), cmp);    // use heap to optimze
}

*p = 0;
return buff;
}
``````
Copy The Code &

Input

cmd
s = "aab"

Output

cmd
"aba"

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String reorganizeString(String s) {
Map map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
PriorityQueue < Character> pq = new PriorityQueue<>(
(o1, o2) -> map.get(o2).compareTo(map.get(o1)));
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
char removed = pq.poll();
if (!sb.isEmpty() && sb.charAt(sb.length() - 1) == removed) {
if (pq.isEmpty()) {
return "";
}
char secondRemoved = pq.poll();
sb.append(secondRemoved);
} else {
sb.append(removed);
}
}
return sb.toString();
}

private void updateStructure(Map < Character, Integer> map, PriorityQueue pq, char c) {
map.put(c, map.get(c) - 1);
if (map.get(c) > 0) {
} else {
map.remove(c);
}
}
}
``````
Copy The Code &

Input

cmd
s = "aab"

Output

cmd
"aba"

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const reorganizeString = function (s) {
const freq = Array(26).fill(0)
const a = 'a'.charCodeAt(0), n = s.length
for(const e of s) {
freq[e.charCodeAt(0) - a]++
}
let max = 0, maxIdx = 0
for(let i = 0; i  <  26; i++) {
if(freq[i] > max) {
max = freq[i]
maxIdx = i
}
}

if(max > (n + 1) / 2) return ''

const res = Array(n)

let idx = 0
while(freq[maxIdx]) {
res[idx] = String.fromCharCode(a + maxIdx)
idx += 2
freq[maxIdx]--
}

for(let i = 0; i < 26; i++) {
while(freq[i]> {
if(idx >= n) idx = 1
res[idx] = String.fromCharCode(i + a)
idx += 2
freq[i]--
}
}

return res.join('')
}
``````
Copy The Code &

Input

cmd
s = "aaab"

Output

cmd
""

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def reorganizeString(self, S):
cnt, res = collections.Counter(S), ""
while len(res) < len(S):
c, i = cnt.most_common()[0], 0
while i + 1 < len(cnt) and (res and res[-1] == c[0] or cnt[c[0]] == 0): c, i = cnt.most_common()[i + 1], i + 1
if not cnt[c[0]] or res and res[-1] == c[0]: return ""
else: res, cnt[c[0]] = res + c[0], cnt[c[0]] - 1
return res
``````
Copy The Code &

Input

cmd
s = "aaab"

Output

cmd
""

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0767_ReorganizeString
{
public string ReorganizeString(string S)
{
var counts = new int[26];
foreach (var ch in S)
counts[ch - 'a']++;

var pairs = new (char ch, int count)[26];
for (int i = 0; i  <  26; i++)
pairs[i] = ((char)('a' + i), counts[i]);
Array.Sort(pairs, (p1, p2) => p2.count.CompareTo(p1.count));

if (pairs[0].count > (S.Length + 1) / 2) return string.Empty;

var result = new char[S.Length];
var index = 0;
foreach ((var ch, var count) in pairs)
{
if (count == 0) break;

for (int i = 0; i  <  count; i++)
{
result[index] = ch;
index += 2;
if (index >= S.Length) index = 1;
}
}

return new string(result);
}
}
}
``````
Copy The Code &

Input

cmd
s = "aab"

Output

cmd
"aba"