Show problems as
Classic problem #1405MediumStringGreedyHeap (Priority Queue)

Longest Happy String

Real-world version: The Longest Row of Tiles With No Triple
Tracked in this browser only
Read Longest Happy String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Three trays hold lettered tiles: a tiles stamped 'a', b tiles stamped 'b' and c tiles stamped 'c'.

Lay tiles out in a row, taking no more from a tray than it holds, so that nowhere in the row does the same letter appear three times running.

Return the longest row that can be laid, written as the string of its letters. Where several rows tie for longest, return the one that comes first in dictionary order.

Examples

Example 1

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

The lone `a` and lone `b` open three places for `c` tiles, counting the two ends, and each place holds at most two, so only six of the seven `c` tiles can be laid and the row runs to eight tiles. Opening with `a` would strand one more `c` tile, so the dictionary-first row of that length starts with a pair of `c` tiles.

Example 2

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

The single `b` tile splits the row into two places for `a` tiles, each holding at most two, so four of the seven `a` tiles go down and the row runs to five.

Example 3

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

No tray is dominant enough to leave anything stranded, so all five tiles are laid, and taking the earliest letter possible at each step gives the dictionary-first way of doing it.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_diverse_string(a: int, b: int, c: int) -> str:
Java
public String longestDiverseString(int a, int b, int c)

More on the same topics