0019EasyArrayStringTrie

Shared Crate Code

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 depot stencils a lowercase code onto every crate in a shipment. codes lists one code per crate, in the order the crates were loaded, and a crate whose stencil ran dry carries an empty code.

Return the longest opening run of characters that all of the codes begin with. The run is matched front to back and position by position: its first character must be the first character of every code, its second character must be the second character of every code, and so on for as far as the agreement holds.

When the codes already part ways at their opening character, or when any crate in the shipment carries an empty code, the answer is the empty string "".

A shipment can consist of one crate, and then that crate's own code is the whole answer.

Examples

Example 1

Input: codes = ["shipment", "shipping", "ship"]
Output: "ship"

All three begin with s, h, i, p. The fifth position holds m, p and nothing at all, so the run stops after four characters, exactly the length of the shortest code.

Example 2

Input: codes = ["crate", "box", "pallet"]
Output: ""

The opening characters are c, b and p, so the agreement is empty before it starts.

Example 3

Input: codes = ["solo"]
Output: "solo"

A lone crate agrees with itself over its full code.

Constraints

1 <= codes.length <= 200
0 <= codes[i].length <= 200
codes[i] is made of lowercase English letters when it is not empty

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 shared_crate_code(codes: list[str]) -> str:

Java

public String sharedCrateCode(String[] codes)

The intended approach

Time O(n * m) where n is the crate count and m the shortest code lengthSpace O(m)

Hold the first code as a running candidate and fold each remaining code into it. Comparing a code against the candidate can only ever shorten the candidate, so walk the two forward together and cut the candidate at the first position where they differ or where either one runs out. A candidate that reaches length zero can never grow again, so return immediately at that point.

Pythonentry point: shared_crate_code

def shared_crate_code(codes):
    candidate = codes[0]
    for code in codes[1:]:
        limit = min(len(candidate), len(code))
        matched = 0
        while matched < limit and candidate[matched] == code[matched]:
            matched += 1
        candidate = candidate[:matched]
        if not candidate:
            return ""
    return candidate

The obvious version

Grow a candidate one character at a time off the shortest code and keep the longest candidate that every code starts with, testing each candidate against the whole shipment, O(n * m^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_shared_crate_code(codes):
    shortest = min(codes, key=len)
    best = ""
    for end in range(len(shortest) + 1):
        candidate = shortest[:end]
        if all(code.startswith(candidate) for code in codes):
            best = candidate
    return best

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