1405. Longest Happy String - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given three integers a, b, and c representing the maximum number of occurrences of the characters 'a', 'b', and 'c' respectively. Your task is to return the longest happy string that can be formed using these characters.

A string is considered happy if it does not contain any of these three substrings: "aaa", "bbb", or "ccc" (i.e. no three identical consecutive characters).

Note:

You do not have to use all the characters.
If no happy string can be constructed, return an empty string.

Examples

Example 1

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation:
One possible valid string is "ccaccbcc". It uses at most 1 'a', 1 'b', and 7 'c' (here 7 'c' are available, but not all may be used). The string does not contain "ccc" consecutively (there are never three 'c' in a row), nor does it have three consecutive 'a' or 'b'.

Example 2

Input: a = 2, b = 2, c = 1
Output: "aabbc" (or any valid arrangement, e.g., "ababc")
Explanation:
The output string uses at most the given counts and is happy because it does not contain three identical consecutive characters.

Hints

Greedy Approach:
- Use a max-heap (priority queue) to always choose the character with the highest remaining count.
- Before appending the chosen character, check if adding it would cause three consecutive identical letters.
- If it would, try using the next highest count character instead.
- If no alternative is available, the process stops.
Alternative Approaches:
- An iterative greedy solution (without an explicit heap) can also work by manually comparing counts.
- A recursive/backtracking method exists, but it is less efficient given the problem’s constraints.

Approach 1: Greedy with Max-Heap (Optimal)

Idea

Max-Heap Setup:
- Create a max-heap of pairs (count, char) for 'a', 'b', and 'c' (use negative counts in Python since its heap is a min-heap).
Building the Result:
- Repeatedly extract the character with the highest count.
- If the last two characters in the result are equal to this candidate, then try the next candidate.
- Append the chosen character and decrement its count.
- Push back any character that still has a positive count.
Termination:
- Stop if no character can be appended without breaking the happy condition.

Complexity Analysis

Time Complexity: O(n log 3) ≈ O(n), where n is the length of the result string (since the heap size is constant—at most 3).
Space Complexity: O(n) for the result string and O(1) extra space for the heap (only three elements).

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Alternative Approaches

Approach 2: Iterative Greedy Without Heap

Another alternative is to iteratively select the next character by comparing counts directly (since there are only 3 characters). Although not as elegant as using a heap, it works well for this problem size.

Complexity Analysis

Time Complexity: O(n) where n is the length of the result string.
Space Complexity: O(n) for the result string.

Common Mistakes & Edge Cases

Three Consecutive Same Characters:
The key is to prevent adding a character if the last two characters in the result are the same.
Running Out of Options:
When the top candidate would cause three in a row and no other candidate exists, the loop must break to avoid an invalid string.
Not Using a Greedy Approach:
Some try to use recursion or dynamic programming which can be overkill. The greedy approach with a heap is both efficient and clear.
Input where one or two characters have zero count:
Make sure to handle cases where one or more of a, b, or c are zero.

Longest Happy String Variants:
Similar problems where a string must be formed under constraints, such as avoiding certain substrings.
Reorganize String (LeetCode 767):
A problem where you must rearrange characters so that no two adjacent characters are the same.
Task Scheduler (LeetCode 621):
Involves scheduling tasks with cooldown periods, which is conceptually similar in terms of avoiding “too many in a row.”

Summary

The Longest Happy String problem can be efficiently solved using a greedy algorithm with a max-heap. This approach ensures that at each step, the character with the highest remaining count is used unless it would cause three consecutive identical letters, in which case an alternative is chosen.

TAGS

leetcode

CONTRIBUTOR

Design Gurus Team