DSA problem
Longest Happy String
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', at most b occurrences of the letter 'b', and at most c occurrences of the letter 'c'.
Given three integers a, b, and c, return any 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.
The greedy idea is intuitive: at every step we should try to append the letter that still has the largest remaining count, because that letter is most likely to "run out of room" later if we delay it. A max-heap keyed by remaining count lets us pull the most-available letter in O(log 3) per step.
The wrinkle is the no-triple constraint. If the last two letters of the result are already equal to the heap's top letter, appending it would create three in a row. The fix: pull the top letter; if appending it would violate the rule, pull the next letter instead (if one exists), append a single instance of it, and put both letters back on the heap with their updated counts. The loop terminates when the heap is empty or the only available letter would form a triple — at that point the string is as long as possible.
Examples
a = 1, b = 1, c = 7"ccaccbcc"a = 7, b = 1, c = 0"aabaa"a = 2, b = 2, c = 1"aabbc"Constraints
- 0 <= a, b, c <= 100
- a + b + c > 0
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.