Custom Sort String

Medium · strings

A librarian shelves books by a house ranking of letters. You are given order, a string of distinct lowercase letters that lists some letters from most to least important, and a string s of lowercase letters.

Rearrange the letters of s into a new string using these rules:

Letters that appear in order come first, in the same order as in order. All copies of one letter sit together.
Letters of s that do not appear in order come after those, in ordinary alphabetical order.

Return the rearranged string. It uses exactly the letters of s, each as many times as s has it.

Examples

Example 1

Input: order = "kqep", s = "pekeq"

Output: "kqeep"

Following the ranking k, q, e, p gives "k", "q", "ee", "p".

Example 2

Input: order = "ba", s = "cabbxa"

Output: "bbaacx"

The two "b" come first, then the two "a". The letters "c" and "x" are not ranked, so they follow in alphabetical order.

Example 3

Input: order = "z", s = "cab"

Output: "abc"

No letter of s is ranked, so all of them are in alphabetical order.

Constraints

1 <= len(order) <= 26
1 <= len(s) <= 10^4
order and s contain only lowercase English letters.
The letters of order are all different.