Algorithm
Problem Name: 767. Reorganize String
Problem Link: https://leetcode.com/problems/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 <= 500sconsists 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;
}
Input
s = "aab"
Output
"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)));
pq.addAll(map.keySet());
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();
pq.add(removed);
sb.append(secondRemoved);
updateStructure(map, pq, secondRemoved);
} else {
sb.append(removed);
updateStructure(map, pq, 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) {
pq.add(c);
} else {
map.remove(c);
}
}
}
Input
s = "aab"
Output
"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('')
}
Input
s = "aaab"
Output
""
#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
Input
s = "aaab"
Output
""
#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);
}
}
}
Input
s = "aab"
Output
"aba"