0038EasyHash TableStringSorting

Matching Letter Tally

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 print shop sets words from loose metal type. The string tray lists the pieces of type sitting in a tray, one lowercase letter per piece, and the string target is the word a customer wants set.

The compositor may reorder the pieces freely but may not fetch a new piece or leave one out. Return true when the tray can be re-set to spell target exactly, and false otherwise.

Because each piece is a physical object, how many times a letter occurs matters: a tray holding two a pieces cannot set a word that needs three, even though both use the same letters.

Examples

Example 1

Input: tray = "cellar", target = "caller"
Output: true

Both words need one c, one a, two l, one e and one r, so the same pieces serve either arrangement.

Example 2

Input: tray = "aabb", target = "abbb"
Output: false

The tray and the word draw on the same two letters, but the word calls for three b pieces and the tray holds two.

Example 3

Input: tray = "zz", target = "z"
Output: false

Setting the word would leave a piece unused, which is not allowed.

Constraints

1 <= tray.length, target.length <= 5 * 10^4
tray and target contain lowercase English letters only

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 can_respell(tray: str, target: str) -> bool:

Java

public boolean canRespell(String tray, String target)

The intended approach

Time O(n)Space O(1)

Unequal lengths settle it immediately, since every piece must be used exactly once. Otherwise tally each letter of the tray, spend one from the tally for each letter of the word, and reject as soon as a tally would go negative. With equal lengths and no shortfall, every tally lands back at zero.

Pythonentry point: can_respell

def can_respell(tray, target):
    if len(tray) != len(target):
        return False
    tally = {}
    for piece in tray:
        tally[piece] = tally.get(piece, 0) + 1
    for letter in target:
        left = tally.get(letter, 0)
        if left == 0:
            return False
        tally[letter] = left - 1
    return True

The obvious version

Sort both strings and compare them character by character. Two multisets of letters are equal exactly when their sorted forms match. O(n log n).

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_can_respell(tray, target):
    return sorted(tray) == sorted(target)

How this problem was checked

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