Longest Happy String
Longest Happy String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.
Problem statement
Implement the Solution class and its longestDiverseString method. The method receives three nonnegative counts: a for the available letter 'a', b for 'b', and c for 'c'.
A happy string contains only the letters 'a', 'b', and 'c', uses no more than the available count of any letter, and never contains three identical letters consecutively. The string may use fewer copies of a letter than its corresponding parameter.
Return any happy string with maximum possible length. If no non-empty happy string can be formed, return the empty string "". The answer does not need to be unique.
Example 1:
Input: a = 2, b = 1, c = 0 Output: "aab" Explanation: The string uses all available letters and never has three equal consecutive characters, so its length is maximal.
Example 2:
Input: a = 5, b = 1, c = 1 Output: "aabaaca" Explanation: All seven available letters can be arranged without creating aaa, making this a longest happy string.
Example 3:
Input: a = 0, b = 0, c = 4 Output: "cc" Explanation: At most two c characters can be consecutive, so only two of the four available characters can be used.
Constraints:
- a, b, and c are JSON integers. - 0 0.
Topics and companies
Topics: Heap, Greedy, String, Counting.
How to practise Longest Happy String on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O((a + b + c) log 3), which is O(a + b + c). time and O(1), since the priority queue contains at most three letters. space.
Open Longest Happy String in the code editor, or read the Longest Happy String editorial for a worked solution with its approach and complexity analysis.
Where Longest Happy String sits in the DSA pattern sheet
- Heap (Priority Queue) Patterns pattern guide
- Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Longest Happy String
Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:
- Furthest Building You Can Reach — Medium, same subpattern
- IPO — Hard, same subpattern
- Maximum Average Pass Ratio — Medium, same subpattern
- Meeting Rooms II — Medium, same subpattern
- Meeting Rooms III — Hard, same subpattern
- Minimum Cost to Hire K Workers — Hard, same subpattern