0463EasyHash TableString

Does The Shift Code Fit The Bin Run

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 sorting line is set up from two written records of the same shift. code is a string of lowercase letters, one letter per item that came down the line. run names the bin each item was dropped into, the bin names given as lowercase words separated by single spaces, with no space at either end.

The two records fit when the letters and the bin names stand in for each other exactly: every occurrence of a given letter goes with the same bin name, and every occurrence of a given bin name goes with the same letter. So one letter may not cover two different bins, and one bin may not answer to two different letters. The two records must also describe the same number of items.

Return true if the two records fit and false otherwise. A bin name is one whole word: two names that merely share a first letter are different names.

Examples

Example 1

Input: code = "mnm", run = "rust amber rust"
Output: true

The letter m goes with rust both times it appears and n goes with amber, and neither bin is shared with another letter.

Example 2

Input: code = "pq", run = "amber amber"
Output: false

The two letters are different but both items went into amber, so one bin would have to answer to two letters.

Example 3

Input: code = "wzwz", run = "chalk slate slate chalk"
Output: false

The letter w goes with chalk and z with slate at the first two items, and the last two items reverse that pairing.

Constraints

1 <= code.length <= 300
code contains only lowercase English letters.
1 <= run.length <= 3000
run contains only lowercase English letters and the space character ' '.
run has no leading or trailing space.
The bin names in run are separated by exactly one space.

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 code_fits_run(code: str, run: str) -> bool:

Java

public boolean codeFitsRun(String code, String run)

The intended approach

Time O(c + r) over the lengths of the two records.Space O(c + r) for the split names and the two maps.

Split the run into bin names and reject the pair straight away if the two records count different numbers of items. Then step through the pairs keeping two maps, letter to bin and bin to letter. A letter already in the first map must be going to the same bin as before; a fresh letter must be going to a bin that no other letter has claimed.

Pythonentry point: code_fits_run

def code_fits_run(code, run):
    # Hold both directions of the pairing at once: a letter that has already
    # claimed a bin cannot take another, and a bin already claimed cannot answer
    # to a second letter.
    # O(total characters) time, O(distinct letters + distinct bins) space.
    bins = run.split(" ")
    if len(bins) != len(code):
        return False
    letter_to_bin = {}
    bin_to_letter = {}
    for letter, name in zip(code, bins):
        if letter in letter_to_bin:
            if letter_to_bin[letter] != name:
                return False
        elif name in bin_to_letter:
            return False
        else:
            letter_to_bin[letter] = name
            bin_to_letter[name] = letter
    return True

The obvious version

Rewrite each record as a list of numbers by replacing every entry with the position at which that entry first appeared, then compare the two lists. The lookup is a linear scan, so O(n^2).

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_code_fits_run(code, run):
    bins = run.split(" ")
    if len(bins) != len(code):
        return False

    def shape(items):
        order = []
        first = []
        for it in items:
            hit = -1
            for k in range(len(order)):
                if order[k] == it:
                    hit = k
                    break
            if hit == -1:
                order.append(it)
                hit = len(order) - 1
            first.append(hit)
        return first

    return shape(list(code)) == shape(bins)

How this problem was checked

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