Custom Sort String: Hash Map Counting Approach

Custom Sort String (LeetCode 791) gives you two strings: order and s. Your job is to permute the characters of s so that they appear in the same relative order as they do in order. Any characters in s that do not appear in order can be placed at the end in any position.

For example, given order = "cba" and s = "abcd", you return "cbad". The characters c, b, and a follow the priority defined by order, and d (not in order) gets appended at the end.

Why this problem matters

Custom Sort String is a clean example of the "count and reconstruct" pattern. Instead of using a comparator or sorting function, you count the characters in s and then rebuild the string by iterating through order. This sidesteps comparison sorting entirely and gives you linear time.

The pattern shows up in many problems where you need to rearrange characters according to some external rule. Once you recognize that counting lets you reconstruct in any order you want, problems like Sort Characters By Frequency and Reorganize String become much easier to approach.

This problem also reinforces a fundamental hash map skill: using a frequency map not just to answer queries, but to drive construction of a new output.

The approach

The idea is simple. First, count every character in s using a hash map. Then, walk through order one character at a time. For each character in order, if it exists in your count map, append it to the result as many times as its count indicates, and remove it from the map. After you have processed every character in order, whatever remains in the count map are characters that were not mentioned in order. Append those at the end in any order.

This works because order defines the priority sequence for the characters it contains. By pulling characters out in the order that order specifies, you guarantee the correct relative ordering. Characters not in order have no ordering constraint, so they can go anywhere at the end.

Clean solution

from collections import Counter

def custom_sort_string(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)

Step-by-step walkthrough

Let's trace through the example with order = "cba" and s = "abcd". First, you build the count map: {'a': 1, 'b': 1, 'c': 1, 'd': 1}. Then you iterate through order. At 'c', you append "c" once and remove it from the map. At 'b', you append "b" once. At 'a', you append "a" once. Now the map has only {'d': 1} left. You append "d" at the end. The final result is "cbad".

If s had duplicate characters, say s = "aabcd", the count map would show {'a': 2, 'b': 1, 'c': 1, 'd': 1}. When you reach 'a' in order, you would append "aa" (two copies). The logic handles duplicates naturally because you always append ch * count[ch].

Complexity analysis

Here n is the length of s and m is the length of order. Building the count map takes O(n). Walking through order takes O(m). Appending remaining characters takes O(n) in the worst case. The space is O(n) for the count map and the result string.

The building blocks

1. Frequency counting with a hash map

Count how many times each character appears in a string. This is the same building block used in Group Anagrams, Valid Anagram, and Sort Characters By Frequency. Python's Counter does this in one line:

from collections import Counter

count = Counter(s)

2. Order-driven reconstruction

Once you have the counts, you iterate through a separate sequence (here, order) and use the counts to emit characters in the right order. This is different from sorting by frequency. Instead of sorting by count, you are sorting by position in an external string. The reconstruction loop looks like this:

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

The del statement ensures you do not double-count characters when you append the remaining ones at the end.

Edge cases to watch for

• Characters in order not in s. If order contains 'z' but s does not, the loop simply skips it because 'z' is not in the count map.
• Characters in s not in order. These get appended at the end after the ordered portion. Their relative order does not matter.
• Duplicate characters in s. The count map naturally handles duplicates. If 'a' appears 5 times, you append "aaaaa" when you process 'a' from order.
• Empty order string. If order is empty, the first loop does nothing and you return s in its original character order (or any permutation, since no ordering is specified).
• All characters of s are in order. The second loop has nothing to append. The result is entirely determined by order.

From understanding to recall

The counting step is familiar territory. You have built frequency maps many times. The part that can slip away under pressure is remembering to iterate through order first instead of iterating through the count map. It feels natural to sort the map or use a comparator, but the cleaner path is to let order drive the reconstruction directly.

Spaced repetition helps lock in that sequence: count first, then walk through the external ordering, then handle leftovers. After a few reps at increasing intervals, this three-phase pattern becomes automatic. You will recognize it the moment you see a problem that says "arrange according to a custom rule."

Related posts

• Sort Characters By Frequency - Another custom ordering problem using counting
• Group Anagrams - Hash map character counting for grouping
• Isomorphic Strings - Character mapping between two strings