A string s is called happy if it satisfies the following conditions:
s only contains the letters 'a', 'b', and 'c'.s does not contain any of "aaa", "bbb", or "ccc" as a substring.s contains at most a occurrences of the letter 'a'.s contains at most b occurrences of the letter 'b'.s contains at most c occurrences 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 > 0Problem 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.
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:
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.
Python
C++
Java
C#
JavaScript
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).
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.
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.
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).
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Longest Happy String - Leetcode 1405 - Python • NeetCode • 36,551 views views
Watch 9 more video solutions →Practice Longest Happy String with our built-in code editor and test cases.
Practice on FleetCode