Longest Happy String - Solution & Explanation
Problem Statement
A string s is called happy if it satisfies the following conditions:
sonly contains the letters'a','b', and'c'.sdoes not contain any of"aaa","bbb", or"ccc"as a substring.scontains at mostaoccurrences of the letter'a'.scontains at mostboccurrences of the letter'b'.scontains at mostcoccurrences of the letter'c'.
Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: a = 1, b = 1, c = 7 Output: "ccaccbcc" Explanation: "ccbccacc" would also be a correct answer.
Example 2:
Input: a = 7, b = 1, c = 0 Output: "aabaa" Explanation: It is the only correct answer in this case.
Constraints:
0 <= a, b, c <= 100a + b + c > 0
Approach Overview
Problem Overview: Given counts of characters a, b, and c, build the longest possible string where no character appears three times consecutively. The result can use any combination of these letters, but sequences like "aaa", "bbb", or "ccc" are not allowed.
Approach 1: Greedy Approach with Priority Queue (Time: O(n log 3), Space: O(1))
The core idea is always picking the character with the highest remaining frequency while preventing three identical characters in a row. Store the counts of a, b, and c in a max heap (priority queue). Each step removes the most frequent character and appends it to the result unless the last two characters already match it. If that happens, take the second-most frequent character instead, append it, and push both entries back with updated counts. Because the heap size never exceeds three elements, heap operations are effectively constant. This greedy strategy works because delaying the most frequent character only when necessary preserves future flexibility. The algorithm runs in O(n log 3) time, which simplifies to O(n), and uses O(1) extra space aside from the output string.
This solution relies on a greedy decision process combined with a heap (priority queue) to always select the best available character. The string construction itself is straightforward iteration over the total character count.
Approach 2: Simulated Annealing Strategy (Time: ~O(n * iterations), Space: O(n))
A less common but interesting strategy treats the problem as an optimization task. Start with a candidate string built from all available characters and repeatedly perform small modifications, such as swapping characters or adjusting positions. Each modification is evaluated based on how many valid characters remain without forming forbidden triples. Using simulated annealing, the algorithm occasionally accepts worse states early in the process to escape local optima, then gradually becomes stricter as the temperature decreases.
This probabilistic search can eventually converge to a near‑optimal or optimal happy string. However, its runtime depends on the number of iterations and randomness, typically around O(n * k) where k is the number of annealing steps. It also requires O(n) space to maintain candidate strings. While educational for exploring optimization techniques on string problems, it is rarely used in interviews because deterministic greedy solutions are simpler and faster.
Recommended for interviews: The greedy priority queue approach is the expected solution. It demonstrates control over heap operations, careful handling of constraints, and the ability to enforce rules while maximizing length. Showing the brute reasoning first (always pick the largest count but avoid triples) and then implementing it with a heap signals strong algorithmic thinking.
Approach 1: Greedy Approach with Priority Queue
This approach utilizes a max heap (or priority queue) to always try to append the character with the highest remaining count without breaking the "happy" condition. Here’s the detailed plan:
- Initialize a max heap to store pairs of (remaining count, character) for 'a', 'b', and 'c'. Only characters with a positive count are inserted into the heap to start.
- Pick the character with the largest count from the heap (say it’s 'X'). If you already have two 'X's at the end of the answer string, you should not append 'X' again directly.
- If 'X' can be used, decrement its remaining count and append it to the result.
- If 'X' cannot be directly used (because you already have two 'X's), pick the second most abundant character from the heap and append it instead, then continue.
- Adjust the count for the characters in the heap and re-adjust the heap structure if needed.
Once you process all characters when the heap is non-empty, the constructed string is your answer.
The function longestDiverseString uses a max heap to store the characters and their counts as negative values (since Python’s heapq is a min-heap). We always take two checks before appending: If the same character was used twice consecutively before, we opt for the next available character (if any). After appending a character, if there are still instances of this character left, we push it back into the heap with the updated count. This ensures the resulting string is as long as possible and never violates the 'happy' conditions.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n log k), where n is the total number of characters (sum of a, b, c) and k is the number of non-zero count characters (at most 3).
Space Complexity: O(1), as we are only storing a fixed number of elements in the heap (at most 3 with their counts).
Approach 2: Simulated Annealing Strategy
This strategy incorporates the concepts of simulated annealing where the decision of which character to append is softly randomized, guided by the need to form a balanced happy string using all the available characters maximally — performing a structured simulation of building the string dynamically and reevaluating choices iteratively.
The C++ code builds potential "happy" strings by iterating through all possible orders of appending triplet combinations. For each order (swapping item positions within "abc"), potential outcomes are evaluated with respect to happy constraints and count tracking. The code iteratively improves upon choices to achieve maximal string formations.
Complexity
Time Complexity: O(k! * n), where k = 3 (permutations of distinct characters) and n denotes total character appearances.
Space Complexity: O(1), only a few data structures to hold options.
Approach 3: Greedy + Priority Queue
The greedy strategy is to prioritize the selection of characters with the most remaining occurrences. By using a priority queue or sorting, we ensure that the character selected each time is the one with the most remaining occurrences (to avoid having three consecutive identical characters, in some cases, we need to select the character with the second most remaining occurrences).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Priority Queue | Time Complexity: O(n log k), where n is the total number of characters (sum of a, b, c) and k is the number of non-zero count characters (at most 3). Space Complexity: O(1), as we are only storing a fixed number of elements in the heap (at most 3 with their counts). |
| Simulated Annealing Strategy | Time Complexity: O(k! * n), where k = 3 (permutations of distinct characters) and n denotes total character appearances. Space Complexity: O(1), only a few data structures to hold options. |
| Greedy + Priority Queue | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Priority Queue | O(n log 3) ≈ O(n) | O(1) | Best general solution. Efficiently builds the longest valid string while preventing three consecutive characters. |
| Simulated Annealing Strategy | ~O(n * k) | O(n) | Useful for experimentation with probabilistic optimization, not typically used in interviews. |
Video Solution
Longest Happy String - Leetcode 1405 - Python • NeetCode • 37,932 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Happy String easy or hard?
How to solve Longest Happy String in O(n)?
Longest Happy String Python or Java solution?
What is the best approach for Longest Happy String?
What data structure is used in Longest Happy String?
What is the time complexity of Longest Happy String?
Is Longest Happy String asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Longest Happy String with our built-in code editor and test cases.
Practice on FleetCode