Custom Sort String

Problem Description

You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously. Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string. Return any permutation of s that satisfies this property.

Key Insights

• The characters in order dictate the sorting of characters in s.
• Characters in s that are not present in order can appear anywhere in the result.
• We can use a hash table to map the characters in order to their indices for sorting.
• The solution can be achieved in linear time relative to the size of s.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of s and m is the length of order.
Space Complexity: O(m), where m is the length of order (for the hash table).

Solution

To solve the problem, we can follow these steps:

1. Create a hash table (dictionary) to store the index of each character in order.
2. Split the characters of s into two groups: those that are in order and those that are not.
3. Sort the characters that are in order based on their indices in the hash table.
4. Append the characters that are not in order to the end of the sorted list.
5. Join the list to form the final sorted string.

We will use a list for the output to maintain character order and a hash table to quickly look up character indices.

Code Solutions