0442EasyHash TableStringBit ManipulationSorting

The Sort That Joined the Tray

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 hand-press shop stores its metal letter sorts loose in a tray. Before a print run the apprentice empties the tray and writes down each sort as a lowercase letter, in whatever order the sorts came to hand; that record is before. After the run one extra sort has been dropped into the tray, and the apprentice empties it and writes it down again, once more in whatever order the sorts came to hand; that record is after.

So after holds every sort that before holds, in some order, plus exactly one more. Neither record tells you anything about where in the tray a sort was sitting, and the extra sort may well be a letter the tray already held several of.

Return the letter of the sort that was added, as a single-character string.

Examples

Example 1

Input: before = "lull", after = "llulu"
Output: "u"

Both writings hold three `l` sorts, but the later one holds two `u` sorts where the earlier one held a single `u`.

Example 2

Input: before = "", after = "q"
Output: "q"

The tray was empty before the job, so the one sort written down afterwards is the sort that was dropped in.

Example 3

Input: before = "dq", after = "adq"
Output: "a"

The `d` and the `q` appear once in each writing, and the later writing carries an `a` that the earlier one has nothing to match.

Example 4

Input: before = "spandrel", after = "landpress"
Output: "s"

Every letter appears the same number of times in both writings apart from `s`, which turns up twice after the job and once before it.

Constraints

0 <= before.length <= 1000
after.length == before.length + 1
before and after consist of lowercase English letters.
after is a rearrangement of before with one extra letter inserted.

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 added_sort(before: str, after: str) -> str:

Java

public char addedSort(String before, String after)

The intended approach

Time O(n) where n is the length of the later record: one pass over each record plus a fixed 26-slot scan.Space O(1): twenty-six tallies, whatever the size of the tray.

Hold one tally per letter of the alphabet, count every sort in the later record up and every sort in the earlier record down, then read off the single letter left standing above zero. Because the later record is a rearrangement of the earlier one plus one sort, no other tally can end up positive, and the order the sorts were written in never enters into it.

Pythonentry point: added_sort

def added_sort(before, after):
    # Keep one running tally per letter of the alphabet: count up for every sort
    # in the later writing and down for every sort in the earlier one. Because
    # the later writing is the earlier one plus a single sort, every tally lands
    # on zero except the added letter, whose tally lands on one. Order inside
    # either writing never matters, so a single pass over each is enough.
    # O(n) time, O(1) space: 26 tallies regardless of how full the tray is.
    tally = [0] * 26
    base = ord("a")
    for ch in after:
        tally[ord(ch) - base] += 1
    for ch in before:
        tally[ord(ch) - base] -= 1
    for slot in range(26):
        if tally[slot] > 0:
            return chr(base + slot)
    return ""

The obvious version

Put both records in alphabetical order and walk them together, reporting the first position where they part company; if they agree the whole way along, the extra sort is the last letter of the longer record.

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_added_sort(before, after):
    first = sorted(before)
    second = sorted(after)
    for i in range(len(first)):
        if first[i] != second[i]:
            return second[i]
    return second[-1]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 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