0099HardArrayStringDepth-First SearchBreadth-First SearchGraph TheoryTopological SortDirected Acyclic Graph

Lost Collation Order

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 retired records system stored its index keys under a custom collation: someone had fixed a private ranking of the symbols, and the system sorted keys by comparing symbols left to right using that ranking, exactly the way a dictionary works. The only surviving artefact is keys, a dump of the index already sorted under that collation, in non-decreasing order. The ranking table itself is gone.

Each key is written with lowercase English letters used as symbols. Rebuild the ranking: return a string that holds every distinct symbol appearing in keys exactly once, written from lowest rank to highest.

A dump usually pins down only part of the ranking, so more than one string can explain it. When that happens, return whichever of those strings comes first when they are compared as ordinary English text. If no ranking of the symbols could have produced the given dump, return an empty string.

Examples

Example 1

Input: keys = ["cb", "ca", "ab"]
Output: "bca"

The first two keys share their opening symbol, so `b` outranks `a` below `c`; the last two show `c` outranks `a` at the opening symbol. That forces `b` and `c` ahead of `a`, and `bca` is the first such string in ordinary text order.

Example 2

Input: keys = ["kite", "kits", "sun"]
Output: "eiknstu"

The dump only reveals that `e` precedes `s` and that `k` precedes `s`. Every other symbol floats freely, so the earliest ordinary-text string honouring those two facts wins.

Example 3

Input: keys = ["dip", "di"]
Output: ""

A key cannot be listed ahead of one of its own openings, whatever the ranking is, so nothing explains this dump.

Constraints

1 <= keys.length <= 100
1 <= keys[i].length <= 100
keys[i] consists of lowercase English letters only
Return the string that comes first in ordinary English text order among all rankings consistent with keys, or "" when none is consistent

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 collation_order(keys: list[str]) -> str:

Java

public String collationOrder(String[] keys)

The intended approach

Time O(L + k^2) where L is the total length of the keys and k the number of distinct symbolsSpace O(k^2)

Each neighbouring pair in the dump reveals at most one fact: at their first differing position, the symbol in the earlier key outranks the symbol in the later key. If one key runs out while matching and it is the longer of the two, the dump is impossible. Treat the facts as edges and grow the answer symbol by symbol, always taking the smallest symbol that currently has no unmet predecessor, which is what makes the result first in ordinary text order. If some symbol never becomes available, the facts form a loop and no ranking exists.

Pythonentry point: collation_order

import heapq


def collation_order(keys):
    symbols = set()
    for key in keys:
        symbols.update(key)
    later = {c: set() for c in symbols}
    unmet = {c: 0 for c in symbols}
    for earlier, following in zip(keys, keys[1:]):
        split = -1
        for i in range(min(len(earlier), len(following))):
            if earlier[i] != following[i]:
                split = i
                break
        if split == -1:
            if len(earlier) > len(following):
                return ""
            continue
        low, high = earlier[split], following[split]
        if high not in later[low]:
            later[low].add(high)
            unmet[high] += 1
    available = [c for c in symbols if unmet[c] == 0]
    heapq.heapify(available)
    ranking = []
    while available:
        c = heapq.heappop(available)
        ranking.append(c)
        for nxt in sorted(later[c]):
            unmet[nxt] -= 1
            if unmet[nxt] == 0:
                heapq.heappush(available, nxt)
    if len(ranking) != len(symbols):
        return ""
    return "".join(ranking)

The obvious version

Walk every permutation of the distinct symbols in ordinary text order and keep the first one under which the dump really is sorted, checking each neighbouring pair by rewriting both keys as rank sequences. Factorial time, but it needs no reasoning about edges at all.

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_collation_order(keys):
    from itertools import permutations
    symbols = sorted(set("".join(keys)))
    for candidate in permutations(symbols):
        rank = {c: i for i, c in enumerate(candidate)}
        sorted_ok = True
        for earlier, following in zip(keys, keys[1:]):
            if [rank[c] for c in earlier] > [rank[c] for c in following]:
                sorted_ok = False
                break
        if sorted_ok:
            return "".join(candidate)
    return ""

How this problem was checked

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