# 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:

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


Example 2:

Input: s = "aaab"
Output: ""


Constraints:

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

## Solutions

• class Solution {
public String reorganizeString(String s) {
int[] cnt = new int[26];
int mx = 0;
for (char c : s.toCharArray()) {
int t = c - 'a';
++cnt[t];
mx = Math.max(mx, cnt[t]);
}
int n = s.length();
if (mx > (n + 1) / 2) {
return "";
}
int k = 0;
for (int v : cnt) {
if (v > 0) {
++k;
}
}
int[][] m = new int[k][2];
k = 0;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
m[k++] = new int[] {cnt[i], i};
}
}
Arrays.sort(m, (a, b) -> b[0] - a[0]);
k = 0;
StringBuilder ans = new StringBuilder(s);
for (int[] e : m) {
int v = e[0], i = e[1];
while (v-- > 0) {
ans.setCharAt(k, (char) ('a' + i));
k += 2;
if (k >= n) {
k = 1;
}
}
}
return ans.toString();
}
}

• class Solution {
public:
string reorganizeString(string s) {
vector<int> cnt(26);
for (char& c : s) ++cnt[c - 'a'];
int mx = *max_element(cnt.begin(), cnt.end());
int n = s.size();
if (mx > (n + 1) / 2) return "";
vector<vector<int>> m;
for (int i = 0; i < 26; ++i) {
if (cnt[i]) m.push_back({cnt[i], i});
}
sort(m.begin(), m.end());
reverse(m.begin(), m.end());
string ans = s;
int k = 0;
for (auto& e : m) {
int v = e[0], i = e[1];
while (v--) {
ans[k] = 'a' + i;
k += 2;
if (k >= n) k = 1;
}
}
return ans;
}
};

• class Solution:
def reorganizeString(self, s: str) -> str:
n = len(s)
cnt = Counter(s)
mx = max(cnt.values())
if mx > (n + 1) // 2:
return ''
i = 0
ans = [None] * n
for k, v in cnt.most_common():
while v:
ans[i] = k
v -= 1
i += 2
if i >= n:
i = 1
return ''.join(ans)


• func reorganizeString(s string) string {
cnt := make([]int, 26)
for _, c := range s {
t := c - 'a'
cnt[t]++
}
mx := slices.Max(cnt)
n := len(s)
if mx > (n+1)/2 {
return ""
}
m := [][]int{}
for i, v := range cnt {
if v > 0 {
m = append(m, []int{v, i})
}
}
sort.Slice(m, func(i, j int) bool {
return m[i][0] > m[j][0]
})
ans := make([]byte, n)
k := 0
for _, e := range m {
v, i := e[0], e[1]
for v > 0 {
ans[k] = byte('a' + i)
k += 2
if k >= n {
k = 1
}
v--
}
}
return string(ans)
}

• use std::collections::{ HashMap, BinaryHeap, VecDeque };

impl Solution {
pub fn reorganize_string(s: String) -> String {
let mut map = HashMap::new();
let mut pq = BinaryHeap::new();
let mut ret = String::new();
let mut queue = VecDeque::new();
let n = s.len();

// Initialize the HashMap
for c in s.chars() {
map.entry(c)
.and_modify(|e| {
*e += 1;
})
.or_insert(1);
}

// Initialize the binary heap
for (k, v) in map.iter() {
if 2 * *v - 1 > n {
return "".to_string();
} else {
pq.push((*v, *k));
}
}

while !pq.is_empty() {
let (v, k) = pq.pop().unwrap();
ret.push(k);
queue.push_back((v - 1, k));
if queue.len() == 2 {
let (v, k) = queue.pop_front().unwrap();
if v != 0 {
pq.push((v, k));
}
}
}

if ret.len() == n {
ret
} else {
"".to_string()
}
}
}