Sorting strings with "before" and "after" constraints
Construct a directed graph in which $a \to b$ if $a$ is constrained to appear before $b$. Run a topological search. If it finds a directed cycle, there is no solution. Otherwise, it gives you some canonical solution.