1004MediumStringGreedyHeap (Priority Queue)

The Longest Row of Tiles With No Triple

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_diverse_string(a: int, b: int, c: int) -> str:

Java

public String longestDiverseString(int a, int b, int c)

The intended approach

Time O(a + b + c) — a fixed amount of arithmetic per tile laid.Space O(a + b + c) for the row being built.

First, how long can a row get? Take any one letter and imagine all the tiles of the other two laid out. They open one more place than there are of them, counting the two ends, and each place holds at most two of the chosen letter before a triple appears. So that letter can spare at most twice the places, and whatever it holds beyond that is stranded. The longest row is therefore everything left less the worst such surplus, and when no letter is that dominant the row uses every tile. The same counting works partway along a row, which is what makes it useful. Given what the trays still hold, plus the letter just laid and how many times running it was laid, that letter loses part of the first place: one slot if it went down once, both if twice. Every other letter is limited by the places as before. That gives the longest row still reachable from where you stand, in a few pieces of arithmetic. Now build the row one tile at a time. At each step try the letters in dictionary order and lay the first one that has a tile left, does not make a triple, and leaves a position from which the rest of the target length is still reachable. Taking the smallest possible letter at the earliest place it is possible is exactly what dictionary order asks for, and the reachability test is what stops a greedy early choice from cutting the row short.

Pythonentry point: longest_diverse_string

def longest_diverse_string(a, b, c):
    def reach(left, last, run):
        total = left[0] + left[1] + left[2]
        short = 0
        for which in range(3):
            have = left[which]
            places = total - have
            room = 2 * places + 2
            if which == last:
                room = 2 * places + (2 - run)
            if have - room > short:
                short = have - room
        return total - short
    left = [a, b, c]
    target = reach(left, -1, 0)
    row = []
    last = -1
    run = 0
    while len(row) < target:
        moved = False
        for which in range(3):
            if left[which] == 0:
                continue
            if which == last and run == 2:
                continue
            step = run + 1 if which == last else 1
            left[which] -= 1
            if 1 + reach(left, which, step) == target - len(row):
                row.append(chr(97 + which))
                last = which
                run = step
                moved = True
                break
            left[which] += 1
        if not moved:
            break
    return "".join(row)

The obvious version

Search the trays outright. A position is what the trays still hold together with the letter just laid and how many times running. From a position, try every letter that has a tile and does not make a triple, take the best row from what follows, and keep the best overall, best meaning longest and then first in dictionary order. Remember the answer for each position so it is worked out once. Costs a stored row per position rather than arithmetic per tile.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_diverse_string(a, b, c):
    seen = {}
    def best(left, last, run):
        key = (left, last, run)
        if key in seen:
            return seen[key]
        answer = ""
        for which in range(3):
            if left[which] == 0:
                continue
            if which == last and run == 2:
                continue
            step = run + 1 if which == last else 1
            nxt = list(left)
            nxt[which] -= 1
            tail = chr(97 + which) + best(tuple(nxt), which, step)
            if len(tail) > len(answer) or (len(tail) == len(answer) and tail < answer):
                answer = tail
        seen[key] = answer
        return answer
    return best((a, b, c), -1, 0)

How this problem was checked

Reference solution executed against 20 test cases — 20 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in