Is Longest Happy String easy or hard?

Longest Happy String is rated Medium difficulty. The challenge comes from enforcing the "no three consecutive characters" constraint while maximizing length. Once the greedy heap idea is recognized, the implementation becomes straightforward.

How to solve Longest Happy String in O(n)?

Build the result greedily while tracking remaining counts of 'a', 'b', and 'c'. Use a max heap to repeatedly choose the character with the largest count, but skip it if the last two characters in the string are the same. If that happens, use the second-largest count instead. Because the heap size is only three, the algorithm behaves like O(n) time.

Longest Happy String Python or Java solution?

Both Python and Java implementations use the same greedy heap strategy. Python typically uses the heapq module with negative counts to simulate a max heap, while Java uses PriorityQueue with a custom comparator. The logic remains identical: repeatedly append the highest-count character unless it would form three consecutive letters.

What is the best approach for Longest Happy String?

The greedy approach using a priority queue is the best solution. It always selects the character with the highest remaining count while ensuring the last two characters in the result do not create a triple. The heap guarantees efficient selection of the next candidate. This approach runs in O(n log 3) time, effectively O(n), with constant auxiliary space.

What data structure is used in Longest Happy String?

The typical implementation uses a max heap (priority queue) to track the remaining counts of each character. The heap allows efficient retrieval of the character with the largest frequency while dynamically updating counts after each append operation.

What is the time complexity of Longest Happy String?

The optimal greedy heap solution runs in O(n log 3) time, where n is the total number of characters (a + b + c). Since the heap contains at most three elements, log 3 is constant, making the overall runtime effectively O(n). Space complexity is O(1) excluding the output string.

Is Longest Happy String asked at Google, Amazon, or Meta?

Variants of this greedy string construction problem appear in interviews at companies like Google and Amazon. Interviewers use it to evaluate understanding of greedy strategies, priority queues, and constraint-based string building.

Description Hints 2 Solution Video 13:10

1405. Longest Happy String

Medium65.5% acceptance8 companies

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 <= 100
a + b + c > 0

Asked at 8 companies

Wayfair Tiktok Capgemini Geico Amazon Microsoft

Google Bloomberg

Topics

Hints open one at a time

Hint 1

Use a greedy approach.

Hint 2

Use the letter with the maximum current limit that can be added without breaking the condition.

13:10

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution