Custom sort string: order characters by a given order

Given an order string of distinct characters and a string s, rearrange s so that its characters that appear in order come first, grouped and arranged as order lists them. The characters of s that are not in order follow, in the order they had in s.

Interface

Unless you agree on a different interface with the interviewer, assume:

• custom_sort(order: str, s: str) -> str

Example

custom_sort("cba", "abcd")       ->  "cbad"
custom_sort("kqep", "pekeq")     ->  "kqeep"     # k, q, e, e, p
custom_sort("ba", "aabbcc")      ->  "bbaacc"
custom_sort("ab", "zaybxa")      ->  "aabzyx"    # z, y, x keep their order from s
custom_sort("", "xyz")           ->  "xyz"

Constraints

• The characters of order are distinct. Either string may be empty.
• O(len(order) + len(s)) time.

Clarifying questions

• Where do characters missing from order go: at the end in their original order, or anywhere?
• Can s repeat characters?
• Are uppercase and lowercase the same character?
• Is the alphabet ASCII or full Unicode?

What a strong answer covers

• A count of each character of s that appears in order, and a separate buffer for the others in their original order. Then emit order with each character repeated by its count, followed by the buffer.
• O(len(order) + len(s)) time, O(alphabet) space for the counts plus the output.
• Why a sort with a custom key works too (O(n log n)), and that only a stable sort keeps the rest in place.
• Unicode: iterate over code points (or grapheme clusters if needed) and key the counts by them.
• Tests: empty order, empty s, characters of order absent from s, every character absent from order.

Follow-ups

• Case-insensitive ordering that still outputs the original characters.
• Check whether a list of words is sorted under a custom alphabet.
• order has duplicates or conflicting rules.