Solution: Custom Sort String

Statement

Given two strings, order and s, where all characters in order are unique and arranged in a custom order, return any permutation of s that satisfies the following condition:

The characters in the permuted s should appear in the same relative order as they do in order. Specifically, if a character x appears before a character y in order, then x must also appear before y in the permuted string.

Constraints:

• $1 \leq$ order.length $\leq 26$

• $1 \leq$ s.length $\leq 200$

• order and s consist of lowercase English letters.

• All the characters of order are unique.

Solution

An optimal way for solving this problem is to first count the occurrences of each character in s using a hash map. Then, iterate through the characters in order, appending as many occurrences of each character to the result string based on its frequency in s. Finally, append any remaining characters from s that were not in order to the result string.

Using the above intuition, the solution can be implemented as follows:

1. Create a hash map, frequencies, to store the count of each character in s. Here, the key is the character itself and the value is the number of times it appears in s.

2. Iterate through s and update frequencies with the count of occurrences of each character.

3. Define result to build the final string.

4. For each character c in order, if it's present in frequencies, append it to result as many times as its recorded frequency. After that, remove it from frequencies.

5. After processing all characters in order, loop through the remaining characters in frequencies. For each character and its count, append it to result.

6. Return result which represents the permuted s satisfying the given condition.

Let’s look at the following illustration to get a better understanding of the solution: