The shade chart

A paint counter names its blends by gluing shorter shade names together. The chart does not say which names are blends, so you have to read that back out of the names themselves.

The problem

A paint shop's chart lists shade names, all lowercase letters, all distinct. Some are base shades, mixed straight from pigment. The rest are blends, and the naming rule is strict: a blend's name is two or more names already on the chart written end to end, with nothing between them. With sea and foam listed, seafoam is a legal blend name; a name may be used twice, so ink makes inkink legal too.

Report every name on the chart that is a blend. A name that reads only as one whole piece is a base shade, however promising its opening looks.

Input. chart — a list of distinct names, lowercase letters.

Output. The blend names, sorted alphabetically.

Example.

chart = ["sea", "foam", "seafoam", "seaweed", "moss", "green", "mossgreen", "sun"]
->  ["mossgreen", "seafoam"]

seafoam is sea + foam and mossgreen is moss + green. seaweed opens with the chart name sea, but weed is not on the chart, so it is a base shade.

A second example, where the longest opening piece is the wrong one:

chart = ["ice", "iceblue", "bluerose", "icebluerose"]
->  ["icebluerose"]

Cutting icebluerose after the longest name that fits, iceblue, leaves rose, which is not on the chart. Cutting after ice leaves bluerose, which is. iceblue itself is a base shade: blue was never listed.

Constraints.

• 1 <= len(chart) <= 10^4
• 1 <= len(name) <= 30, lowercase a-z, names distinct
• total characters across the chart at most 6 * 10^5

Hints

Approach

Brute force

A name of length L has 2^(L−1) ways to cut it, each checked piece by piece against a set. At L = 30 that is 5 · 10⁸ cut sets for one name, and the chart holds 10⁴ names.

The insight

Whether the rest of a name can be spelled depends only on where the last cut fell, not on how the name got there — so one boolean per position replaces the search over cut sets.

The pieces are laid down left to right and never overlap, so two ways of spelling the first i letters leave the same job behind: spell the rest. That collapses 2^(L−1) cut sets to L positions. The trie supplies the moves between them — from position i, one walk spells the remainder a letter at a time, and every end marker passed on the way is a cut you can reach, found in one pass instead of L substring lookups.

The "two or more" rule needs no counter: the only one-piece split runs from 0 to the last letter, so skipping that single end marker rules it out.

Algorithm

1. Build one trie over the whole chart, with an end marker on each name's last node.
2. For a name of length n, keep reachable[0..n], all False but reachable[0].
3. For each i where reachable[i] is True, walk the trie from the root over the name from i onward, stopping when a letter has no child.
4. Whenever that walk stands on an end marker at position j, set reachable[j + 1], unless i is 0 and j is the last letter — that is the name itself.
5. The name is a blend when reachable[n] is True. Collect those and sort.

Complexity

Time O(S + N · L²) — one pass over S total characters to build, then at most L walks of L steps per name, so 900 steps each at L = 30. Space O(S) for the trie, plus a table of L booleans reused per name.

Solution

"""The shade chart — a prefix tree walked from every reachable cut point."""

# Names are lowercase letters only, so "#" is safe as the end-of-name marker.
END = "#"


def build(names):
    """One node per distinct prefix of the whole chart."""
    root = {}
    for name in names:
        node = root
        for ch in name:
            node = node.setdefault(ch, {})
        node[END] = True
    return root


def is_blend(root, name):
    n = len(name)
    # reachable[i] is True when name[:i] can be spelled with chart names.
    # How it was spelled never matters, only that it was.
    reachable = [False] * (n + 1)
    reachable[0] = True

    for i in range(n):
        if not reachable[i]:
            continue
        node = root
        for j in range(i, n):
            node = node.get(name[j])
            if node is None:
                break                       # no chart name starts here
            if END in node and not (i == 0 and j == n - 1):
                # Skipping the one whole-name match is what enforces "two or
                # more parts": every other split has at least two pieces.
                reachable[j + 1] = True
    return reachable[n]


def solve(chart):
    root = build(chart)
    return sorted(name for name in chart if is_blend(root, name))

TESTS = [
    # "seaweed" opens with the chart name "sea" and still is not a blend.
    (
        (["sea", "foam", "seafoam", "seaweed", "moss", "green", "mossgreen", "sun"],),
        ["mossgreen", "seafoam"],
    ),
    # Cutting after the longest name that fits ("iceblue") dead-ends on "rose";
    # cutting after "ice" works. "iceblue" itself is not a blend: no "blue".
    ((["ice", "iceblue", "bluerose", "icebluerose"],), ["icebluerose"]),
    # A name may be reused inside a blend, and a blend may have three parts.
    ((["ink", "inkink", "blueinkink", "blue"],), ["blueinkink", "inkink"]),
    # One name on the chart splits into nothing.
    ((["rose"],), []),
    # No name is a prefix of another: nothing can be a blend.
    ((["sea", "moss", "sun"],), []),
    # Shortest possible names, where reuse is the only way to build a blend.
    ((["a", "aa", "aaa"],), ["aa", "aaa"]),
]

Pitfalls

• Forgetting to exclude the whole name. Every name trivially spells itself in one piece, so without that one skipped marker the answer is the entire chart.
• Stopping the walk at the first end marker. On icebluerose the walk from position 0 passes ice and then iceblue; taking only the last, or only the first, and moving on loses the split that works. Record every marker.
• Marking a position because a node exists. The node for seaw exists because seaweed is on the chart. Marking reachable positions without testing the end marker makes every name a blend.

Variants

• Filling the grid — one walk per query with blanks in the pattern, instead of many walks with cuts in the name.
• The dispatch console — the same tree carrying a ranking at every node rather than a marker at the ends.