HeapProblem 9 of 18
Leetcode reorganize strings
Problem Statement
Given a string s, rearrange the characters so that any two adjacent characters are not the same. Return any valid arrangement or empty string if not possible.
Example:
-
Input:
s = "aab" -
Output:
"aba" -
Explanation: 'a' and 'a' are not adjacent.
-
Input:
s = "aaab" -
Output:
"" -
Explanation: No valid arrangement exists.
Approach 1: Sorting by Frequency (Brute Force)
Intuition
Sort characters by their frequency. Place the most frequent character first, then alternate with others.
Algorithm
- Count frequency of each character
- Sort characters by frequency (descending)
- Try to place characters alternately
- If any character has frequency > (n+1)/2, return ""
java
import java.util.*;
public class Solution {
public String reorganizeString(String s) {
int n = s.length();
Map<Character, Integer> freq = new HashMap<>();
// Count frequencies
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
// Check if valid arrangement is possible
for (int count : freq.values()) {
if (count > (n + 1) / 2) {
return "";
}
}
// Create list of (frequency, character) pairs
List<int[]> chars = new ArrayList<>();
for (Map.Entry<Character, Integer> e : freq.entrySet()) {
chars.add(new int[]{e.getValue(), e.getKey()});
}
// Sort by frequency (descending)
chars.sort((a, b) -> b[0] - a[0]);
// Fill result
char[] result = new char[n];
int idx = 0;
for (int[] p : chars) {
int count = p[0];
char c = (char) p[1];
while (count > 0) {
if (idx >= n) {
idx = 1;
}
result[idx] = c;
idx += 2;
count--;
}
}
return new String(result);
}
}Complexity Analysis
- Time Complexity: O(n log n) - Sorting characters by frequency
- Space Complexity: O(n) - For result string and frequency map
Approach 2: Max-Heap (Optimal)
Intuition
Use a max-heap to always pick the character with highest remaining frequency. After placing a character, if it still has remaining count, hold it and place the next most frequent character, then add the held character back.
Algorithm
- Count frequencies and add to max-heap
- Pop two most frequent characters
- Place both in result
- Push back characters with remaining count
- Handle edge cases when only one character remains
java
import java.util.*;
public class Solution {
public String reorganizeString(String s) {
int n = s.length();
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
// Max-heap: {frequency, character}
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> b[0] - a[0]
);
for (Map.Entry<Character, Integer> e : freq.entrySet()) {
if (e.getValue() > (n + 1) / 2) {
return "";
}
maxHeap.offer(new int[]{e.getValue(), e.getKey()});
}
StringBuilder result = new StringBuilder();
while (maxHeap.size() >= 2) {
// Pop two most frequent
int[] first = maxHeap.poll();
int[] second = maxHeap.poll();
result.append((char) first[1]);
result.append((char) second[1]);
// Push back if still has remaining count
if (first[0] > 1) {
maxHeap.offer(new int[]{first[0] - 1, first[1]});
}
if (second[0] > 1) {
maxHeap.offer(new int[]{second[0] - 1, second[1]});
}
}
// Handle last character
if (!maxHeap.isEmpty()) {
result.append((char) maxHeap.peek()[1]);
}
return result.toString();
}
}Complexity Analysis
- Time Complexity: O(n log k) - n characters, each heap operation is O(log k) where k is unique characters
- Space Complexity: O(k) - Heap contains at most k unique characters (at most 26 for lowercase letters)
Approach 3: Interleaving with Cooldown
Intuition
Similar to task scheduler problem. Place characters with a "cooldown" period using a queue to track when a character can be used again.
Algorithm
- Use max-heap for character selection
- Use queue to track characters in cooldown
- Process one position at a time
java
import java.util.*;
public class Solution {
public String reorganizeString(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
// Max-heap
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> b[0] - a[0]
);
for (Map.Entry<Character, Integer> e : freq.entrySet()) {
maxHeap.offer(new int[]{e.getValue(), e.getKey()});
}
StringBuilder result = new StringBuilder();
int[] prev = {0, '#'};
while (!maxHeap.isEmpty() || prev[0] > 0) {
if (maxHeap.isEmpty() && prev[0] > 0) {
return "";
}
int[] curr = maxHeap.poll();
result.append((char) curr[1]);
curr[0]--;
if (prev[0] > 0) {
maxHeap.offer(prev);
}
prev = curr;
}
return result.toString();
}
}Complexity Analysis
- Time Complexity: O(n log k) - n iterations, log k for heap operations
- Space Complexity: O(k) - Heap and frequency map
Key Takeaways
- Impossible condition: Max frequency > (n+1)/2 means adjacent same characters unavoidable
- Max-heap naturally gives us the most frequent character to place
- Cooldown pattern: After placing a character, hold it before returning to heap
- Even-odd filling: Alternative approach fills even indices first, then odd
- This is LeetCode 767 and appears frequently in interviews
- Similar pattern applies to Task Scheduler (LeetCode 621)
- For strings with only lowercase letters, k ≤ 26, so log k is effectively constant