Leetcode Daily Question 16/10/2024 - 1405. Longest Happy String

Problem Description:

A string s is called happy if it satisfies the following conditions: | --------------------------------------------------------- | s only contains the letters 'a', 'b', and 'c'. | --------------------------------------------------------- | s does not contain any of "aaa", "bbb", or "ccc" as a substring. | --------------------------------------------------------- | s contains at most a occurrences of the letter 'a'. | --------------------------------------------------------- | s contains at most b occurrences of the letter 'b'. | --------------------------------------------------------- | s contains at most c occurrences of the letter 'c'. | --------------------------------------------------------- | Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "". | --------------------------------------------------------- | A substring is a contiguous sequence of characters within a string.

class Solution:
  def longestDiverseString(self, a: int, b: int, c: int) -> str:
    max_heap = []
    if a > 0:
      heapq.heappush(max_heap, (-a, "a"))
    if b > 0:
      heapq.heappush(max_heap, (-b, "b"))
    if c > 0:
      heapq.heappush(max_heap, (-c, "c"))
      
    result = []
    
    while max_heap:
      curr_freq, curr_char = heapq.heappop(max_heap)
      if len(result) >= 2 and result[-1] == result[-2] == curr_char:
        if not max_heap:
          break
        next_freq, next_char = heapq.heappop(max_heap)
        result.append(next_char)
        if next_freq + 1 < 0:
          heapq.heappush(max_heap, (next_freq + 1, next_char))
        heapq.heappush(max_heap, (curr_freq, curr_char))
        
      else:
        result.append(curr_char)
        if curr_freq + 1 < 0:
          heapq.heappush(max_heap, (curr_freq + 1, curr_char))
          
    return "".join(result)

Explanation:

We can solve this problem using a greedy approach, where we always aim to use the letter with the highest remaining frequency to build the result. This ensures that we use the most available letters first while avoiding consecutive repeats of three.

To manage the letter frequencies efficiently, we can use a max-heap (a priority queue), which allows us to always access the letter with the largest frequency. Since Python's heapq is a min-heap by default (which stores the smallest element at the top), we can simulate a max-heap by pushing the negative of each frequency into the heap.

max_heap = []

if a > 0: # Letters with no occurences do not need to be considered.
  heapq.heappush(max_heap, (-a, "a"))
  
if b > 0:
  heapq.heappush(max_heap, (-a, "a"))
  
if c > 0:
  heapq.heappush(max_heap, (-a, "a"))

To build the result, we maintain a list (which is mutable and memory-efficient) to store the individual letters, and later join them into a string. This approach is both space-efficient and easy to manage, as appending to a list is efficient.

The process works by popping the letter with the highest frequency from the max-heap. If using this letter would result in three consecutive identical letters, we temporarily skip it and use the next available letter from the heap. After using the second letter, we push both letters back into the heap (if they still have remaining frequency) to ensure all letters are used as evenly as possible.

The process terminates when no valid letters can be added, i.e., when the heap runs out of elements or all remaining letters would violate the "no three consecutive" rule.

result = []

while max_heap:
  curr_freq, curr_char = heapq.heappop(max_heap)
  if len(result) >= 2 and result[-1] == result[-2] == curr_char:
    if not max_heap: # Cannot break the consective threes rule
      break
    next_freq, next_char = heapq.heappop(max_heap) # Next available character
    result.append(next_char)
    if next_freq + 1 < 0: # The frequency stored in max-heap is negative so we add to it instead of subtract.
      heapq.heappush(max_heap, (next_freq + 1, next_char))
    heapq.heappush(max_heap, (curr_freq, curr_char)) # Push back the original freq and char.
    
  else:
    result.append(curr_char)
    if curr_freq + 1 < 0:
      heapq.heappush(max_heap, (curr_freq + 1, curr_char))
  
  return "".join(result)

The time complexity is O(n), where n = a + b + c. Since the heap contains at most 3 elements, heap operations take O(log 3) ≈ O(1) time. Doing this n times give O(n log 3) ≈ O(n) time.

The space complexity is O(n) as well. This is because we store our result in an array. The maximum length of this array is n.

The full solution can be found near the top of the page.