Show problems as
Classic problem #389EasyHash TableStringBit ManipulationSorting

Find the Difference

Real-world version: The Sort That Joined the Tray
Tracked in this browser only
Read Find the Difference on LeetCode(opens in a new tab)

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

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

Python
def added_sort(before: str, after: str) -> str:
Java
public char addedSort(String before, String after)

More on the same topics