← Back to Heap Pattern

📚 Longest Happy String – Java Cheat Sheet

📌 What Is It?

The problem involves constructing the longest "happy" string using a given number of 'a', 'b', and 'c' characters. A "happy" string is defined as a string where no three consecutive characters are the same.

To solve this efficiently, we use a max-heap to always pick the character with the highest remaining count, ensuring the string remains "happy."

🧱 Pattern Template

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((x, y) -> y[0] - x[0]);
        if (a > 0) maxHeap.offer(new int[]{a, 'a'});
        if (b > 0) maxHeap.offer(new int[]{b, 'b'});
        if (c > 0) maxHeap.offer(new int[]{c, 'c'});

        StringBuilder result = new StringBuilder();

        while (!maxHeap.isEmpty()) {
            int[] first = maxHeap.poll(); // Character with the highest count
            if (result.length() >= 2 && result.charAt(result.length() - 1) == first[1] && result.charAt(result.length() - 2) == first[1]) {
                if (maxHeap.isEmpty()) break; // No other character to use
                int[] second = maxHeap.poll(); // Use the next highest character
                result.append((char) second[1]);
                second[0]--;
                if (second[0] > 0) maxHeap.offer(second);
                maxHeap.offer(first); // Put the first character back
            } else {
                result.append((char) first[1]);
                first[0]--;
                if (first[0] > 0) maxHeap.offer(first);
            }
        }

        return result.toString();
    }
}

📊 Time Complexity

• Heap Initialization: O(1) – Adding up to three characters to the heap.
• Heap Operations: O(n log 3) – For a total of n characters, each heap operation takes O(log 3).
• Overall Complexity: O(n).

✅ Use Cases

• Constructing strings with specific constraints
• Maximizing the length of a string while adhering to rules
• Applications in combinatorics and string manipulation

📘 Common LeetCode Problems

• 1405. Longest Happy String [Medium] Heap

🧪 Example: Longest Happy String

Input: a = 1, b = 1, c = 7
Output: "ccbccacc"

Explanation:
- Use 'c' as much as possible, but avoid three consecutive 'c's.
- Alternate with 'b' and 'a' to maintain the "happy" condition.

▶️ View Animation

💡 Pro Tips

• Use a max-heap to always pick the character with the highest remaining count.
• Edge cases: one or more counts are zero, all counts are equal.
• Ensure the result string adheres to the "no three consecutive characters" rule.