LeetCode 791: Custom Sort String

Problem Restatement

We are given two strings:

order
s

All characters in order are unique.

The string order defines a custom ordering of characters. We need to rearrange the characters of s so that characters appearing in order follow that same relative order.

Characters in s that do not appear in order may be placed anywhere in the result.

Return any valid permutation of s.

Input and Output

Function shape:

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        ...

Examples

Example 1:

order = "cba"
s = "abcd"

The custom order says:

c before b before a

The character d does not appear in order, so it can be placed anywhere.

One valid answer is:

"cbad"

Other valid answers include:

"dcba"
"cdba"
"cbda"

Example 2:

order = "bcafg"
s = "abcd"

The characters from s that appear in order are:

b, c, a

They must appear in that order.

The character d is not in order, so it can be placed anywhere.

One valid answer is:

"bcad"

First Thought: Sort With a Custom Rank

One direct solution is to assign every character in order a rank.

For example:

order = "cba"

gives:

Then we sort the characters of s by this rank.

Characters not in order can receive any default rank, because their position is flexible.

This works, but sorting costs O(n log n).

Since the alphabet is small and lowercase, we can do better with counting.

Key Insight

We do not need comparison sorting.

We only need to place characters from s in the order given by order.

So we can:

1. Count how many times each character appears in s.
2. Append characters that appear in order, following order.
3. Append remaining characters that were not in order.

This is a counting-sort style solution.

Algorithm

1. Count all characters in s.
2. Create an empty list result.
3. For each character ch in order:
   1. Append ch exactly count[ch] times.
   2. Remove it from the count map.
4. Append all remaining characters from the count map.
5. Join the list into a string.

Correctness

The algorithm first counts every character in s, so it knows exactly how many copies of each character must appear in the output.

Then it processes characters in the same order as order. For every character ch in order, the algorithm appends all copies of ch before moving to the next character. Therefore, if character x appears before character y in order, all copies of x are appended before all copies of y.

After that, the algorithm appends characters not present in order. The problem allows these characters to appear anywhere, so placing them at the end is valid.

Every character from s is appended exactly as many times as it appears in s, and no extra characters are added. Therefore, the result is a valid permutation of s that respects the custom order.

Complexity

Let n = len(s) and m = len(order).

The count map stores at most 26 lowercase letters, so auxiliary counting space is O(1) with respect to input size.

Implementation

from collections import Counter

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        count = Counter(s)
        result = []

        for ch in order:
            if ch in count:
                result.append(ch * count[ch])
                del count[ch]

        for ch, freq in count.items():
            result.append(ch * freq)

        return "".join(result)

Code Explanation

We count every character in s:

count = Counter(s)

The result is built as a list of string pieces:

result = []

Then we process order from left to right:

for ch in order:

If ch appears in s, append all its copies:

result.append(ch * count[ch])

Then remove it from the counter so it will not be appended again later:

del count[ch]

Finally, append characters not mentioned in order:

for ch, freq in count.items():
    result.append(ch * freq)

The problem allows these remaining characters to go anywhere, so appending them at the end is valid.

Return the joined string:

return "".join(result)

Alternative: Custom Sorting

A shorter solution uses a rank map and Python sorting.

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        rank = {ch: i for i, ch in enumerate(order)}
        return "".join(sorted(s, key=lambda ch: rank.get(ch, len(order))))

This is concise, but it costs O(n log n) time because it sorts the characters.

Testing

def is_valid(order: str, s: str, result: str) -> bool:
    if sorted(s) != sorted(result):
        return False

    position = {ch: i for i, ch in enumerate(order)}

    filtered = [ch for ch in result if ch in position]

    for i in range(1, len(filtered)):
        if position[filtered[i - 1]] > position[filtered[i]]:
            return False

    return True

def run_tests():
    sol = Solution()

    result = sol.customSortString("cba", "abcd")
    assert is_valid("cba", "abcd", result)

    result = sol.customSortString("bcafg", "abcd")
    assert is_valid("bcafg", "abcd", result)

    result = sol.customSortString("kqep", "pekeq")
    assert is_valid("kqep", "pekeq", result)

    result = sol.customSortString("abc", "xyz")
    assert is_valid("abc", "xyz", result)

    result = sol.customSortString("abc", "aaabbbccc")
    assert is_valid("abc", "aaabbbccc", result)

    print("all tests passed")

run_tests()

Test coverage: