Letterpress tray

A compositor has finished a job and the metal letter tiles come back to the bench in whatever order they were lifted. The tray has to be refilled so the letter used most sits in the front compartment.

The problem

The shop sets lines of type by hand. Every character is a separate metal tile, and when a line is broken up the tiles land in a heap. Refilling the tray means grouping that heap: all copies of one tile together, and the heaviest group first, because the front compartment is the one the hand reaches without looking.

Two tiles are the same only if they print the same glyph, so T and t are different tiles and live in different compartments. When two groups hold the same number of tiles, the shop's rule puts the one whose character comes first in ASCII order in front — digits before capitals, capitals before lowercase.

Return the heap rewritten as one string in tray order.

Input. line — a string of ASCII letters and digits, the tiles as they came off the bench.

Output. A string holding exactly the same tiles, with equal tiles adjacent, groups ordered by size descending and by character ascending on a tie.

Example.

line = "peppermint"   ->  "pppeeimnrt"

Three p tiles lead, then two e. The five singletons follow in ASCII order: i, m, n, r, t.

A second example, where case matters and a tie has to be broken:

line = "Tattoo"   ->  "oottTa"

o and t both appear twice, and o comes first in ASCII, so its compartment goes in front. T is a different tile from t: it stays a group of one, and because capitals sort before lowercase it lands ahead of a.

Constraints.

• 0 <= len(line) <= 10^5
• every character is a-z, A-Z or 0-9, so at most 62 distinct tiles
• the empty heap is a valid input and gives the empty string

Hints

Approach

Brute force

Walk the 62 possible tiles, scanning the whole heap to count each one, then repeatedly pick the largest count not yet emitted: 62 passes over n plus a quadratic pick-the-max loop over the groups — around 6.2 million character reads at n = 100,000, where one pass would do. Sorting the tiles themselves under a frequency comparator is better but still pays n log n comparisons on all 100,000 of them.

The insight

The answer is a function of the tally alone, so counting collapses the input to at most 62 groups and the sort runs on the groups, not on the tiles.

Nothing in the required output depends on where a tile sat in the heap: two heaps with the same tally produce the same tray, so one counting pass is a lossless summary. Sorting 62 groups then costs the same whether n is 60 or 60,000, which is why the log factor attaches to the alphabet and not to the input.

Algorithm

1. Tally the string into (tile, count) pairs in one pass.
2. Sort the pairs by the key (-count, tile) — bigger group first, smaller character code first on a tie.
3. Emit each tile repeated count times and join the pieces.

Complexity

Time O(n + k log k), with n tiles and k ≤ 62 distinct ones — one pass to count, a sort whose size does not grow with n, one pass to build the answer. Space O(n) for the output string; the tally itself is O(k), bounded by 62.

Solution

"""Letterpress tray — tally the tiles, then sort the groups by (-count, tile)."""

from collections import Counter


def solve(line):
    tally = Counter(line)
    # Groups are what gets sorted, not tiles: at most 62 of them however long
    # the line is. Negating the count sorts it downward while the tile itself
    # still sorts upward, which is the tie rule the tray wants.
    groups = sorted(tally.items(), key=lambda pair: (-pair[1], pair[0]))
    return "".join(tile * count for tile, count in groups)

TESTS = [
    (("peppermint",), "pppeeimnrt"),
    (("Tattoo",), "oottTa"),
    (("",), ""),
    (("q",), "q"),
    (("abcabc",), "aabbcc"),
    (("7777",), "7777"),
    (("aA0",), "0Aa"),
]

Pitfalls

• Sorting the characters directly by -count and leaning on stability. Python keeps ties in first-appearance order, so "Tattoo" comes out "ttooTa" — t in front because it appeared earlier. The rule asked for ASCII order, which is a second key, not an accident of the input.
• Normalising case before counting. Lowercasing merges T into t and returns "tttooa", a string containing a tile the shop never had and missing one it did.
• Taking max(tally) on an empty heap. With line = "" the tally is empty and a maximum of nothing raises ValueError; the answer is "".

Variants

• Trailhead campsites — the same two-level tuple key, except both levels run downward and a filter comes first.
• Consecutive van runs — also starts from a tally, but consumes it in a forced order instead of sorting it.