← Back to Index

📚 Reorganize String – Java Cheat Sheet

📌 What Is It?

The Reorganize String problem involves rearranging the characters of a string so that no two adjacent characters are the same. If it is not possible, return an empty string.

This problem can be efficiently solved using a max-heap to track the most frequent characters.

🧱 Pattern Template

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

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()
        );
        maxHeap.addAll(frequencyMap.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() : "";
    }
}

📊 Time Complexity

• Heap Operations: O(N log A) – Adding and removing elements from the heap, where A is the number of unique characters.
• Overall Complexity: O(N log A).

✅ Use Cases

• Reorganizing strings to meet specific constraints
• Applications in scheduling and resource allocation
• Ensuring balanced distribution of elements

📘 Common LeetCode Problems

• 767. Reorganize String [Medium] Heap

🧪 Example: Reorganize String

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

Explanation:
- The most frequent character is 'a'.
- Alternate 'a' with 'b' to ensure no two adjacent characters are the same.

▶️ View Animation

💡 Pro Tips

• Use a max-heap to efficiently track the most frequent characters.
• Edge cases: strings with only one character, strings where reorganization is impossible.
• Ensure the heap stores enough information to track character frequencies.