0753HardArrayStringDynamic ProgrammingDepth-First SearchTrieSorting

Compound Labels In A Parts Catalogue

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 parts catalogue lists labels in labels. Every label is a non-empty string of lowercase letters and no label appears twice.

A label is compound when it can be cut into two or more pieces, laid end to end in order, where every piece is itself a label in the catalogue. The pieces may repeat, so a label may be built by using one catalogue label several times, and the piece order is simply left to right through the compound label. Because a compound label needs at least two pieces and no piece may be empty, every piece is strictly shorter than the compound label it builds.

A label that can only be produced as one whole piece, namely itself, is not compound.

Return every compound label in the catalogue, in any order.

Examples

Example 1

Input: labels = ["ab", "abc", "cd", "abcd"]
Output: ["abcd"]

`"abcd"` cuts into `"ab"` and `"cd"`, two catalogue labels laid end to end. `"abc"` has cuts `"a"` plus `"bc"` and `"ab"` plus `"c"`, and neither pair is in the catalogue. `"ab"` and `"cd"` are two letters each and the catalogue has no single-letter label.

Example 2

Input: labels = ["a", "b", "ab", "ba", "aba", "bab"]
Output: ["ab", "ba", "aba", "bab"]

`"ab"` is `"a"` then `"b"`, `"ba"` is `"b"` then `"a"`, `"aba"` is `"ab"` then `"a"`, and `"bab"` is `"ba"` then `"b"`. The single letters `"a"` and `"b"` cannot be cut into two non-empty pieces at all.

Example 3

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

The catalogue has one label, and it can only be produced as itself in one piece, which the rules do not count.

Constraints

1 <= labels.length <= 10^4
1 <= labels[i].length <= 30
labels[i] consists of lowercase English letters only.
All the labels are different from one another.
The total length of all labels is at most 10^5.

The values you return may be in any order.

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 find_compound_labels(labels: list[str]) -> list[str]:

Java

public List<String> findCompoundLabels(String[] labels)

The intended approach

Time O(sum over labels of L^3) in the worst case for a label of length L, since the reachability scan tries O(L^2) substrings and each costs O(L) to cut out; with L at most 30 that is a small constant multiple of the total input length.Space O(total input length) for the pool, plus O(L) for the reachability flags.

Every piece of a compound label is strictly shorter than the label, so order the catalogue by length and grow a pool of labels already handled. When a label's turn comes the pool holds only labels of its length or less, and since all labels differ, no pool entry can cover the label whole; that makes the two-or-more-pieces rule automatic rather than something to count. For the label itself, mark which cut positions are reachable: position 0 is reachable, and a position is reachable when some earlier reachable position is joined to it by a substring that sits in the pool. The label is compound exactly when its end is reachable. Then drop the label into the pool and move on.

Pythonentry point: find_compound_labels

def find_compound_labels(labels):
    # Handle the labels shortest first. When a label is examined, the pool holds
    # exactly the labels no longer than it, so a reachability scan over cut
    # points can only ever land on genuinely smaller pieces.
    pool = set()
    out = []
    for label in sorted(labels, key=len):
        n = len(label)
        reach = [False] * (n + 1)
        reach[0] = True
        for end in range(1, n + 1):
            for cut in range(end):
                if reach[cut] and label[cut:end] in pool:
                    reach[end] = True
                    break
        if reach[n]:
            out.append(label)
        pool.add(label)
    return out

The obvious version

No sorting and no pool. For each label, take the set of all the other labels and search cut points with an explicit stack, carrying how many pieces have been laid down, and accept the label only when a search reaches its end having used two pieces or more.

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_find_compound_labels(labels):
    """For each label, walk cut points with an explicit stack over the full set of
    the other labels, counting how many pieces have been laid down and accepting
    only when the label is finished with two pieces or more."""
    every = set(labels)
    out = []
    for label in labels:
        others = every - {label}
        n = len(label)
        stack = [(0, 0)]
        visited = set()
        good = False
        while stack:
            pos, pieces = stack.pop()
            if pos == n:
                if pieces >= 2:
                    good = True
                    break
                continue
            key = (pos, pieces if pieces < 2 else 2)
            if key in visited:
                continue
            visited.add(key)
            for end in range(pos + 1, n + 1):
                if label[pos:end] in others:
                    stack.append((end, pieces + 1))
        if good:
            out.append(label)
    return out

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