Longest Happy String

The key idea

Always extend the string with the letter that still has the largest remaining count, unless that letter already sits at the end twice in a row. In that case use the letter with the next-largest count to break the run, then come back to the plentiful letter.

Problem

A string s is called happy if it does not contain any of the substrings "aaa", "bbb", or "ccc".

Given three non-negative integers a, b, and c, return any longest possible happy string that uses at most a letters 'a', at most b letters 'b', and at most c letters 'c'.

You do not have to use all of the letters, and the string may use only some of the three letter kinds. If no happy string of length greater than zero can be formed, return the empty string "". If several answers tie for the longest, return any one of them.

Constraints

0 <= a, b, c <= 100
a + b + c > 0

Examples

Input: a = 1, b = 1, c = 7 Output: "ccaccbcc"

Input: a = 2, b = 2, c = 1 Output: "aabbc"

Input: a = 7, b = 1, c = 0 Output: "aabaa"

Complexity

Time: O(a + b + c) Space: O(a + b + c)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →