Leetcode Problem 1405. Longest Happy String

1405. Longest Happy String

Leetcode Solutions

Greedy Approach with Max Heap

  1. Initialize a max heap to keep track of the counts of 'a', 'b', and 'c'.
  2. Add tuples of the form (-count, char) for each character to the heap, with negative counts to simulate a max heap.
  3. Initialize an empty result string.
  4. While the heap is not empty: a. Pop the character with the highest count from the heap. b. If the last two characters of the result string are the same as this character: i. Pop the next character from the heap. ii. Add this second character to the result string. iii. Increment its count (since we use negative counts) and push it back into the heap if it's not exhausted. iv. Push the first character back into the heap. c. Otherwise, add the first character to the result string and decrement its count. d. If the count of the first character is not exhausted, push it back into the heap.
  5. Return the result string.
UML Thumbnail

Happy Greedy String without Priority Queue

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...