Problem Statement:
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.
Examples:
Example 1:
Input: s = “aab”
Output: “aba”
Example 2:
Input: s = “aaab”
Output: “”
Constraints
1 <= s.length <= 500
s consists of lowercase English letters.
Time Complexity:
Time Complexity = O(n + k log k ) ≈ O(n)
where m is length of the generated string at each step.
Space Complexity:
Space Complexity = O(n)
Approach
- First,
count the frequency of each characterin the string and track the maximum frequency. -
If any character appears more than ⌈n/2⌉ times, it is impossible to rearrange the string without
adjacent duplicates, so return an empty string. - Sort the
characters in descending orderbased on their frequency so that the most frequent characters are placed first. -
Create a result array and start filling characters at even
indices (0, 2, 4, …). Once even positions are filled, continue filling at oddindices (1, 3, 5, …). - This placement ensures that the same characters are spaced apart, preventing
adjacent duplicates. - Finally, join the array to form the reorganized string.
Dry Run
Input: s = "aab"
Initial:
freq = {}
maxFreq = 0
Counting frequency:
c = 'a' → freq['a'] = 1, maxFreq = 1
c = 'a' → freq['a'] = 2, maxFreq = 2
c = 'b' → freq['b'] = 1, maxFreq = 2
freq = { a: 2, b: 1 }
n = 3
Check impossible case:
maxFreq = 2, ceil(3/2) = 2 → valid
Sort characters:
chars = ['a', 'b'] (sorted by frequency desc)
Initialize:
result = [ , , ]
i = 0
Fill characters:
ch = 'a', count = 2
count = 2:
i = 0 → result[0] = 'a'
i = 2
count = 1
count = 1:
i = 2 → result[2] = 'a'
i = 4
count = 0
result = ['a', , 'a']
ch = 'b', count = 1
count = 1:
i = 4 >= n → i = 1
result[1] = 'b'
i = 3
count = 0
result = ['a', 'b', 'a']
Final:
return "aba"
Output: "aba"
var reorganizeString = function(s) {
let freq = {};
let maxFreq = 0;
// Count frequency
for (let c of s) {
freq[c] = (freq[c] || 0) + 1;
maxFreq = Math.max(maxFreq, freq[c]);
}
let n = s.length;
// Impossible case
if (maxFreq > Math.ceil(n / 2)) {
return "";
}
// Sort characters by frequency (descending)
let chars = Object.keys(freq).sort((a, b) => freq[b] - freq[a]);
let result = new Array(n);
let i = 0;
// Fill even indices first, then odd
for (let ch of chars) {
let count = freq[ch];
while (count > 0) {
if (i >= n) {
i = 1; // move to odd index
}
result[i] = ch;
i += 2;
count--;
}
}
return result.join("");
};
def reorganizeString(s):
freq = {}
maxFreq = 0
# Count frequency
for c in s:
freq[c] = freq.get(c, 0) + 1
maxFreq = max(maxFreq, freq[c])
n = len(s)
# Impossible case
if maxFreq > (n + 1) // 2:
return ""
# Sort characters by frequency (descending)
chars = sorted(freq.keys(), key=lambda x: -freq[x])
result = [""] * n
i = 0
# Fill even indices first, then odd
for ch in chars:
count = freq[ch]
while count > 0:
if i >= n:
i = 1
result[i] = ch
i += 2
count -= 1
return "".join(result)
import java.util.*;
class Solution {
public String reorganizeString(String s) {
HashMap freq = new HashMap<>();
int maxFreq = 0;
// Count frequency
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
maxFreq = Math.max(maxFreq, freq.get(c));
}
int n = s.length();
// Impossible case
if (maxFreq > (n + 1) / 2) {
return "";
}
// Sort characters by frequency
List chars = new ArrayList<>(freq.keySet());
chars.sort((a, b) -> freq.get(b) - freq.get(a));
char[] result = new char[n];
int i = 0;
// Fill even indices first, then odd
for (char ch : chars) {
int count = freq.get(ch);
while (count > 0) {
if (i >= n) {
i = 1;
}
result[i] = ch;
i += 2;
count--;
}
}
return new String(result);
}
}
#include <bits/stdc++.h>
using namespace std;
string reorganizeString(string s) {
unordered_map freq;
int maxFreq = 0;
// Count frequency
for (char c : s) {
freq[c]++;
maxFreq = max(maxFreq, freq[c]);
}
int n = s.length();
// Impossible case
if (maxFreq > (n + 1) / 2) {
return "";
}
// Sort characters by frequency
vector chars;
for (auto &p : freq) {
chars.push_back(p.first);
}
sort(chars.begin(), chars.end(), [&](char a, char b) {
return freq[a] > freq[b];
});
vector result(n);
int i = 0;
// Fill even indices first, then odd
for (char ch : chars) {
int count = freq[ch];
while (count--) {
if (i >= n) {
i = 1;
}
result[i] = ch;
i += 2;
}
}
return string(result.begin(), result.end());
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 256
int compare(const void *a, const void *b, void *freq) {
int *f = (int *)freq;
return f[*(char*)b] - f[*(char*)a];
}
char* reorganizeString(char* s) {
int freq[MAX] = {0};
int n = strlen(s);
int maxFreq = 0;
// Count frequency
for (int i = 0; i < n; i++) {
freq[(int)s[i]]++;
if (freq[(int)s[i]] > maxFreq)
maxFreq = freq[(int)s[i]];
}
// Impossible case
if (maxFreq > (n + 1) / 2) {
char* empty = malloc(1);
empty[0] = '\0';
return empty;
}
char chars[MAX];
int idx = 0;
for (int i = 0; i < MAX; i++) {
if (freq[i] > 0) {
chars[idx++] = (char)i;
}
}
// Sort chars by frequency (simple bubble sort for clarity)
for (int i = 0; i < idx; i++) {
for (int j = i + 1; j < idx; j++) {
if (freq[(int)chars[j]] > freq[(int)chars[i]]) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
}
char* result = (char*)malloc(n + 1);
int pos = 0;
for (int k = 0; k < idx; k++) {
int count = freq[(int)chars[k]];
while (count--) {
if (pos >= n) {
pos = 1;
}
result[pos] = chars[k];
pos += 2;
}
}
result[n] = '\0';
return result;
}
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public string ReorganizeString(string s) {
Dictionary freq = new Dictionary();
int maxFreq = 0;
// Count frequency
foreach (char c in s) {
if (!freq.ContainsKey(c))
freq[c] = 0;
freq[c]++;
maxFreq = Math.Max(maxFreq, freq[c]);
}
int n = s.Length;
// Impossible case
if (maxFreq > (n + 1) / 2) {
return "";
}
// Sort characters
var chars = freq.Keys.OrderByDescending(c => freq[c]).ToList();
char[] result = new char[n];
int i = 0;
// Fill even indices first, then odd
foreach (char ch in chars) {
int count = freq[ch];
while (count > 0) {
if (i >= n) {
i = 1;
}
result[i] = ch;
i += 2;
count--;
}
}
return new string(result);
}
}
