Skip to main content

Reorganize String

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.

Example 1​

**Input**: `s = "aab"`

**Output**: `"aba"`

Example 2​

**Input**: `s = "aaab"`

**Output**: `""`

Constraints​

  • (1≤s.length≤500)(1 \leq \text{s.length} \leq 500)
  • s consists of lowercase English letters.

Algorithm​

  1. Counting Frequencies: We count the frequency of each character using Counter.

  2. Max-Heap: We store the frequency as a negative value because heapq in Python is a min-heap. By storing negative values, the character with the highest positive frequency will be at the root of the heap.

  3. Heap Operations: We pop from the heap and append the character to the result. If the previous character still has a remaining count, we push it back into the heap.

  4. Final Check: After constructing the result, we check if its length matches the input string. If not, it's impossible to rearrange the string as required.

Code Implementation​

Solution in Python​

import heapq
from collections import Counter

class Solution:
def reorganizeString(self, s: str) -> str:
freq_map = Counter(s)

# Max heap to store characters by frequency
max_heap = [(-freq, char) for char, freq in freq_map.items()]
heapq.heapify(max_heap)

result = []
prev_freq, prev_char = 0, ''

while max_heap:
freq, char = heapq.heappop(max_heap)
result.append(char)

# If the previous character frequency is > 0, push it back into the heap
if prev_freq < 0:
heapq.heappush(max_heap, (prev_freq, prev_char))

# Decrease frequency and set the previous character to current
prev_freq, prev_char = freq + 1, char

result_str = ''.join(result)

# If the reorganized string is of the same length as the input string, return it
return result_str if len(result_str) == len(s) else ""

C++ Solution​

#include <queue>
#include <unordered_map>
#include <string>

class Solution {
public:
std::string reorganizeString(std::string s) {
std::unordered_map<char, int> freqMap;
for (char c : s) {
freqMap[c]++;
}

std::priority_queue<std::pair<int, char>> maxHeap;
for (auto& pair : freqMap) {
maxHeap.push({pair.second, pair.first});
}

std::string result = "";
std::pair<int, char> prev = {-1, '#'}; // To store the previous character

while (!maxHeap.empty()) {
auto current = maxHeap.top();
maxHeap.pop();

result += current.second;

if (prev.first > 0) {
maxHeap.push(prev);
}

current.first--;
prev = current;
}

return result.size() == s.size() ? result : "";
}
};

Java Solution​

import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Map;

class Solution {
public String reorganizeString(String s) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}

PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(
(a, b) -> b.getValue() - a.getValue());

maxHeap.addAll(freqMap.entrySet());

StringBuilder result = new StringBuilder();
Map.Entry<Character, Integer> prev = null;

while (!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> current = maxHeap.poll();
result.append(current.getKey());

if (prev != null && prev.getValue() > 0) {
maxHeap.offer(prev);
}

current.setValue(current.getValue() - 1);
prev = current;
}

return result.length() == s.length() ? result.toString() : "";
}
}

JavaScript Solution​

function reorganizeString(s) {
const freqMap = {};
for (const char of s) {
freqMap[char] = (freqMap[char] || 0) + 1;
}

const maxHeap = Object.entries(freqMap).map(([char, freq]) => [-freq, char]);
maxHeap.sort((a, b) => a[0] - b[0]);

let result = "";
let prev = null;

while (maxHeap.length > 0) {
const [freq, char] = maxHeap.shift();
result += char;

if (prev && prev[0] < 0) {
maxHeap.push(prev);
maxHeap.sort((a, b) => a[0] - b[0]);
}

prev = [freq + 1, char];
}

return result.length === s.length ? result : "";
}