NeetCode #544LC-1405MediumHeap / Priority QueueNC 250
← Back to All Problems#544 · #1405 · Longest Happy String(最长快乐字符串)
📌 Problem Statement & Constraints
A happy string consists of
a, b, c with no three consecutive identical characters. Given counts a, b, c, return the longest possible happy string, or the empty string if none. Constraints: 0 <= a, b, c <= 100.💡 Core Algorithmic Approaches
- Always append the most frequent available character.
- If doing so would create three in a row, take the second most frequent instead.
- A max-heap of
(count, char)makes the choice O(log 3). - If the second most frequent is unavailable when needed, the string is finished.
💻 Benchmark Python3 Implementation
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
import heapq
h = [(-cnt, ch) for cnt, ch in ((a, "a"), (b, "b"), (c, "c")) if cnt > 0]
heapq.heapify(h)
res = []
while h:
cnt, ch = heapq.heappop(h)
if len(res) >= 2 and res[-1] == ch and res[-2] == ch:
# would create three in a row -> use the second most frequent
if not h:
break
cnt2, ch2 = heapq.heappop(h)
res.append(ch2)
cnt2 += 1
if cnt2 < 0:
heapq.heappush(h, (cnt2, ch2))
heapq.heappush(h, (cnt, ch))
else:
res.append(ch)
cnt += 1
if cnt < 0:
heapq.heappush(h, (cnt, ch))
return "".join(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log 3) = O(n) where n is the output length.
💾 Space Complexity
O(1) for the heap (at most three entries).
⚠️ Interview Pitfalls & Follow-ups
- Taking two of the most frequent character when possible: that is actually optimal, but the simple formulation places one at a time; both work -- the key is the three-in-a-row check.
- Forgetting to push the deferred character back: it would be lost.
- Breaking when the second choice is unavailable: the string is complete at that point, which the
breakhandles. - Ignoring the counts entirely: the answer is bounded by the total counts.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.