0823MediumHash TableStringGreedyCounting

Largest Mirror Number From Tiles

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.

A sign maker owns a tray of digit tiles, listed as the string tiles, one character per tile. The tiles may be laid out in any order, and tiles that are not wanted stay in the tray, but at least one tile must be laid.

The sign must read the same left to right as right to left. It must also read as an ordinary number, so it may not begin with a 0, with one exception: the sign consisting of the single tile 0 is allowed.

Return the largest number the sign maker can lay out, as a string. A longer sign always beats a shorter one, and among signs of the same length the larger number wins. The tray always allows at least one legal sign.

Examples

Example 1

Input: tiles = "614616"
Output: "61616"

The sign `61616` reads the same in both directions and needs three 6 tiles and two 1 tiles, all of which the tray holds. The 4 tile stays in the tray.

Example 2

Input: tiles = "0000"
Output: "0"

Every tile in the tray is a 0, and a sign may not open with a 0 unless it is the single tile `0`, which is the sign laid here.

Example 3

Input: tiles = "550"
Output: "505"

The sign `505` reads the same in both directions, uses both 5 tiles and the 0 tile, and opens with a 5 rather than a 0.

Constraints

1 <= tiles.length <= 10^5
tiles consists of the digit characters '0' through '9' only.
The answer is returned as a string, so it may be far too long to hold in a number.

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 largest_mirror(tiles: str) -> str:

Java

public String largestMirror(String tiles)

The intended approach

Time O(n) for a tray of n tiles.Space O(n) for the sign that is returned.

Only how many tiles the tray holds of each digit matters. Build the left side of the sign digit by digit from 9 downwards, laying each digit's tiles two at a time, one on the left and its mirror on the right, while the 0 tiles are held back until some larger digit has already been laid so the sign cannot open with a 0. Whatever tiles are left over then give the centre, which is the largest digit with an odd number remaining, and a tray that ends up laying nothing at all can still show a single 0.

Pythonentry point: largest_mirror

def largest_mirror(tiles):
    # Tally the tray, then fill the left side from 9 downwards using each digit's
    # tiles two at a time, holding back the 0 tiles until something non-zero has
    # already been placed so the sign never starts with a 0. The centre is then the
    # largest digit with a tile left over, and mirroring the left side finishes it.
    # Time: O(n) for a tray of n tiles.
    # Space: O(n) for the sign that is returned.
    counts = [0] * 10
    for ch in tiles:
        counts[ord(ch) - 48] += 1
    left = []
    for d in range(9, -1, -1):
        pairs = counts[d] // 2
        if pairs and (d > 0 or left):
            left.append(chr(48 + d) * pairs)
            counts[d] -= pairs * 2
    middle = ""
    for d in range(9, -1, -1):
        if counts[d] % 2 == 1:
            middle = chr(48 + d)
            break
    head_part = "".join(left)
    if not head_part and not middle:
        return "0"
    return head_part + middle + head_part[::-1]

The obvious version

Generate every string over the digits the tray holds up to half the tray's length, fold each one into a mirror-reading number both ways round, throw away the ones that open with a 0 or that the tray cannot pay for, and keep the best of what is left.

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_largest_mirror(tiles):
    """Write out every mirror-reading number that could be built from the digits
    present, keep the ones the tray can actually pay for, and take the best. Only
    usable on a short tray, but it assumes nothing at all about how to build one."""
    have = [0] * 10
    for ch in tiles:
        have[ord(ch) - 48] += 1
    pool = [chr(48 + d) for d in range(10) if have[d]]
    n = len(tiles)
    best = ""
    stack = [""]
    halves = []
    # every string over the digits present, up to half the tray length rounded up
    limit = (n + 1) // 2
    while stack:
        cur = stack.pop()
        if cur:
            halves.append(cur)
        if len(cur) < limit:
            for ch in pool:
                stack.append(cur + ch)
    for head_part in halves:
        for cand in (head_part + head_part[::-1], head_part + head_part[-2::-1]):
            if len(cand) > n:
                continue
            if cand[0] == "0" and cand != "0":
                continue
            need = [0] * 10
            for ch in cand:
                need[ord(ch) - 48] += 1
            affordable = True
            for d in range(10):
                if need[d] > have[d]:
                    affordable = False
                    break
            if not affordable:
                continue
            if len(cand) > len(best) or (len(cand) == len(best) and cand > best):
                best = cand
    return best

How this problem was checked

Reference solution executed against 22 test cases — 22 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