HeapProblem 17 of 18
Rearrange characters in a string such that no two adjacent are same
Problem Statement
Given a string with repeated characters, rearrange the characters such that no two adjacent characters are the same. If not possible, return an empty string.
Example:
-
Input:
s = "aaabbc" -
Output:
"ababac"or"abacab"(any valid arrangement) -
Explanation: No two adjacent characters are the same.
-
Input:
s = "aaab" -
Output:
"" -
Explanation: Not possible as 'a' appears 3 times but other characters appear only once.
Approach 1: Sorting by Frequency
Intuition
Sort characters by frequency and place them at alternate positions starting with the most frequent.
Algorithm
- Count frequency of each character
- Sort characters by frequency (descending)
- Place characters at even indices first, then odd indices
- Check if valid arrangement exists: max_freq <= (n+1)/2
java
import java.util.*;
public class Solution {
public String rearrangeString(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
for (int count : freq.values()) {
if (count > (n + 1) / 2) {
return "";
}
}
// Sort by frequency
List<int[]> charList = new ArrayList<>();
for (Map.Entry<Character, Integer> e : freq.entrySet()) {
charList.add(new int[]{e.getValue(), e.getKey()});
}
charList.sort((a, b) -> b[0] - a[0]);
// Fill result
char[] result = new char[n];
int idx = 0;
for (int[] p : charList) {
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) - Due to sorting
- Space Complexity: O(n) - For result string
Approach 2: Max-Heap (Optimal)
Intuition
Use a max-heap to always get the character with highest remaining frequency. Place it, then place the next most frequent character to avoid adjacency.
Algorithm
- Count frequencies and push to max-heap
- Pop two most frequent characters
- Place both in result
- Push back to heap if count > 0
- Handle edge case when only one character remains
java
import java.util.*;
public class Solution {
public String rearrangeString(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
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) {
int[] first = maxHeap.poll();
int[] second = maxHeap.poll();
result.append((char) first[1]);
result.append((char) second[1]);
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]});
}
}
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 O(log k), k = unique chars
- Space Complexity: O(k) - Heap size (at most 26 for lowercase letters)
Approach 3: Using Cooldown Queue
Intuition
After placing a character, put it in a "cooldown" queue. Only after placing another character can we use it again.
Algorithm
- Use max-heap for selection
- After placing a character, hold it in a variable
- Place next character, then add held character back to heap
- This ensures no two adjacent characters are same
java
import java.util.*;
public class Solution {
public String rearrangeString(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
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)
- Space Complexity: O(k)
Key Takeaways
- Validity check: max_frequency <= (n+1)/2
- Max-heap naturally gives most frequent character
- Cooldown pattern: Hold character before adding back to prevent adjacency
- Even-odd placement: Alternative approach fills even indices first
- This is essentially the same as LeetCode 767 - Reorganize String
- Similar pattern applies to Task Scheduler problem
- For k=26 (lowercase letters), log k is effectively constant
- The greedy choice of most frequent character is provably optimal