⚡Flashcard Drill➔
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

  1. Always append the most frequent available character.
  2. If doing so would create three in a row, take the second most frequent instead.
  3. A max-heap of (count, char) makes the choice O(log 3).
  4. 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 break handles.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems