How do you solve Longest Happy String on LeetCode?

Longest Happy String (LeetCode #1405) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Greedy algorithms often yield optimal solutions by making the best choice at each step.

What is the brute force solution for Longest Happy String?

The brute force approach for Longest Happy String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach generates all possible strings using the characters 'a', 'b', and 'c' and checks each one to see if it meets the happy string conditions. This is straightforward but inefficient due to the exponential number of combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Longest Happy String?

Longest Happy String uses the following concepts: String, Greedy, Heap (Priority Queue). The recommended patterns to study are: Greedy, Heap (Priority Queue).

What are the interview tips for Longest Happy String?

Explain your thought process clearly, especially when choosing characters. Discuss edge cases, such as when one or more character counts are zero. Practice writing clean and efficient code, as clarity can be as important as correctness.

What are common mistakes when solving Longest Happy String?

Failing to check for three consecutive characters correctly. Not considering the case where only one character type is available.

#1405

Longest Happy String

Medium

StringGreedyHeap (Priority Queue)GreedyHeap (Priority Queue)

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a greedy approach to build the longest happy string by always adding the character that can be added without violating the happy string conditions. This ensures we maximize the length while adhering to the constraints.

⚙️

Algorithm

3 steps

1Step 1: Initialize an empty string to build the happy string.
2Step 2: While there are characters left to add, choose the character with the highest remaining count that does not create three consecutive characters.
3Step 3: Append the chosen character to the string and update the counts accordingly.

solution.py28 lines

1# Full working Python code
2import heapq
3
4def longest_happy_string(a, b, c):
5    max_heap = []
6    if a > 0:
7        heapq.heappush(max_heap, (-a, 'a'))
8    if b > 0:
9        heapq.heappush(max_heap, (-b, 'b'))
10    if c > 0:
11        heapq.heappush(max_heap, (-c, 'c'))
12
13    result = ""
14    while max_heap:
15        count, char = heapq.heappop(max_heap)
16        if len(result) >= 2 and result[-1] == result[-2] == char:
17            if not max_heap:
18                break
19            next_count, next_char = heapq.heappop(max_heap)
20            result += next_char
21            if next_count + 1 < 0:
22                heapq.heappush(max_heap, (next_count + 1, next_char))
23            heapq.heappush(max_heap, (count, char))
24        else:
25            result += char
26            if count + 1 < 0:
27                heapq.heappush(max_heap, (count + 1, char))
28    return result

ℹ

Complexity note: The time complexity is O(n) because we are processing each character count at most once, and the heap operations are logarithmic in nature but bounded by the number of characters.

1Greedy algorithms often yield optimal solutions by making the best choice at each step.
2Using a max heap helps efficiently manage character counts and ensure the longest happy string.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.