LeetCode Solutions Blog

Longest Happy String

Number: 1304

Difficulty: Medium

Paid? No

Problem Description

Given three integers a, b, and c representing the maximum number of occurrences of 'a', 'b', and 'c' respectively, construct the longest possible string that only consists of these letters without containing any substring of three identical consecutive characters (i.e., "aaa", "bbb", "ccc"). If multiple answers exist, return any of them. If no valid string exists, return an empty string.

Key Insights

Use a greedy strategy to always pick the letter with the highest remaining count unless it would result in three consecutive identical letters.
Use a max-heap (or priority queue) to efficiently retrieve the character with the largest remaining frequency.
If the top element would cause an invalid sequence, select the next best option.
Continue this process until no valid moves remain.

Space and Time Complexity

Time Complexity: O((a+b+c) * log 3) ≈ O(a+b+c) since the heap contains at most 3 elements.
Space Complexity: O(1) additional space, aside from the output string.

Solution

The solution utilizes a greedy algorithm combined with a max-heap (priority queue) to always choose the letter with the highest count. At each step, we check if appending the selected letter causes three consecutive occurrences. If it does, we attempt to use the next most frequent letter instead. This ensures that the longest possible string is constructed without violating the happy string constraints.

Code Solutions

import heapq

def longestDiverseString(a: int, b: int, c: int) -> str:
    # Create a max heap using negative counts (heapq is a min heap by default)
    max_heap = []
    for count, char in [(-a, 'a'), (-b, 'b'), (-c, 'c')]:
        if count < 0:
            heapq.heappush(max_heap, (count, char))
    
    result = []
    
    while max_heap:
        # Get the character with the highest remaining count
        count, char = heapq.heappop(max_heap)
        # Check if appending this character causes three consecutive same characters
        if len(result) >= 2 and result[-1] == result[-2] == char:
            # If no alternative, break out of the loop
            if not max_heap:
                break
            # Use the next most frequent character instead
            count2, char2 = heapq.heappop(max_heap)
            result.append(char2)
            count2 += 1  # Decrease the count (since counts are negative)
            if count2 < 0:
                heapq.heappush(max_heap, (count2, char2))
            # Push the original character back for future consideration
            heapq.heappush(max_heap, (count, char))
        else:
            result.append(char)
            count += 1  # Decrement count (count is negative so adding 1 increases it)
            if count < 0:
                heapq.heappush(max_heap, (count, char))
                
    return "".join(result)

# Example usage:
print(longestDiverseString(1, 1, 7))  # could output "ccaccbcc" or another valid answer