See all coding puzzles and patterns here.

Problem Definition

Given a string s and an order, sort the string s so that its characters match the order in order. order contains each character only once. Any characters that are not in order may appear anywhere in the response. More specifically, sort s so that for every pair of indexes x and y > x in s, the index of s[x] in order is less than or equal to the index of s[y] in order.

Examples

Some test cases to verify our solution.

assert(custom_sort("abacbdgcefdgfe", "abcdefg") == "aabbccddeeffgg")
assert(custom_sort("abacbdgcefdgfe", "gfedcba") == "ggffeeddccbbaa")
# assert(custom_sort("abacbdgcefdgfe", "abcdef") in ("ggaabbccddeeff", "aaggbbccddeeff", ...))

Solution

We will traverse s once to count characters. Then we'll traverse order and generate a string using the character counts for each character in order. 

def custom_order(s: str, order: str) -> str:
    counts = {}
    for c in s:
        counts[c] = counts.get(c, 0) + 1
    ans = []
    for c in order:
        if c in counts:
            ans.append(c * counts[c])
            del counts[c]
    for c in counts:
        ans.append(c * counts[c])
    return "".join(ans)

Complexity

Let $n = $ len(s), $m = $ len(order).

Since we're traversing both s and order once separately (not nested traversals), runtime complexity should be $\Theta(n + m)$.

The string generation logic will generate at most $n$ characters; so auxiliary space complexity should be $O(n)$.