Problem Description

You are given two strings: order and s. The string order contains unique characters that define a custom sorting order. Your task is to rearrange the characters in string s according to this custom order.

The sorting rule is: if character x appears before character y in the order string, then all occurrences of x must appear before all occurrences of y in the rearranged version of s.

For example:

• If order = "cba" and s = "abcd", then "cbad" would be a valid result because:
  • c comes before b in order, so c comes before b in the result
  • c comes before a in order, so c comes before a in the result
  • b comes before a in order, so b comes before a in the result
  • d is not in order, so it can be placed anywhere

Characters in s that don't appear in order can be placed in any position relative to each other, as long as the relative order of characters that do appear in order is maintained.

The solution creates a dictionary mapping each character in order to its index position. Then it sorts string s using this mapping as the sort key. Characters not in order get a default value of 0, placing them at the beginning of the sorted result.

Intuition

The key insight is that we need to sort string s based on a custom ordering rather than the standard alphabetical order. When we think about custom sorting, we need a way to assign each character a "priority" or "rank" that determines its position in the sorted output.

The natural approach is to use the position (index) of each character in the order string as its sorting priority. For instance, if order = "cba", then:

• c has priority 0 (appears at index 0)
• b has priority 1 (appears at index 1)
• a has priority 2 (appears at index 2)

By mapping each character to its index in order, we create a custom comparison key that can be used with Python's built-in sorted() function. Characters with lower index values will appear earlier in the sorted result.

But what about characters in s that don't appear in order? We need to handle these gracefully. The solution assigns them a default priority of 0 using d.get(x, 0). This places all "unspecified" characters at the beginning of the result. We could also place them at the end by using a large default value, or maintain their original relative order - the problem allows any placement for these characters.

The beauty of this approach is its simplicity: we transform the custom ordering problem into a standard sorting problem by creating an appropriate key function. The dictionary lookup d[c] gives us O(1) access to each character's priority, making the overall solution efficient at O(n log n) due to the sorting step.

Learn more about Sorting patterns.

Solution Approach

The implementation uses a dictionary-based mapping combined with Python's sorting capabilities to achieve the custom ordering:

Step 1: Build the Priority Map

d = {c: i for i, c in enumerate(order)}

This creates a dictionary where each character from order maps to its index position. For example, if order = "cba", the dictionary becomes {'c': 0, 'b': 1, 'a': 2}. This gives us O(1) lookup time for character priorities.

Step 2: Sort with Custom Key

sorted(s, key=lambda x: d.get(x, 0))

The sorted() function sorts the characters of string s using a custom key function. For each character x:

• If x exists in the dictionary d, use its mapped value (index from order)
• If x doesn't exist in d, use the default value 0

This ensures characters are sorted according to their position in order, while characters not in order are grouped at the beginning (since they all get priority 0).

Step 3: Join the Result

''.join(sorted(...))

Convert the sorted list of characters back into a string using join().

Time Complexity: O(n log n) where n is the length of string s, dominated by the sorting operation.

Space Complexity: O(m + n) where m is the length of order (for the dictionary) and n is the length of s (for the sorted list).

The algorithm elegantly handles all edge cases:

• Characters appearing multiple times in s maintain their relative grouping
• Characters not in order are handled gracefully with the default value
• The solution works even if s is empty or contains only characters not in order

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• order = "cba"
• s = "abcd"

Step 1: Build the Priority Map

We create a dictionary mapping each character in order to its index:

d = {c: i for i, c in enumerate(order)}
# d = {'c': 0, 'b': 1, 'a': 2}

Step 2: Process Each Character in s

Now let's see how each character in s = "abcd" gets its sorting priority:

Step 3: Sort by Priority

The characters with their priorities are:

• 'a' → priority 2
• 'b' → priority 1
• 'c' → priority 0
• 'd' → priority 0

When sorted by priority (ascending order):

1. 'c' (priority 0) comes first
2. 'd' (priority 0) comes next (same priority as 'c', but 'c' was from order)
3. 'b' (priority 1) comes third
4. 'a' (priority 2) comes last

Step 4: Join the Result

The sorted list ['c', 'd', 'b', 'a'] is joined into the final string: "cdba"

Verification:

• ✓ 'c' appears before 'b' (as specified in order = "cba")
• ✓ 'c' appears before 'a' (as specified in order = "cba")
• ✓ 'b' appears before 'a' (as specified in order = "cba")
• ✓ 'd' is placed at the beginning with other non-ordered characters

The final result "cdba" correctly follows the custom ordering rules!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of string s.

• Creating the dictionary d from order takes O(m) time where m is the length of order
• The sorted() function uses Timsort algorithm which has O(n log n) time complexity for sorting n characters in string s
• The lambda function key=lambda x: d.get(x, 0) is called for each character during sorting, and dictionary lookup is O(1)
• The ''.join() operation takes O(n) time to concatenate the sorted characters
• Overall: O(m) + O(n log n) + O(n) = O(n log n) (assuming n ≥ m in typical cases)

Space Complexity: O(n + m)

• The dictionary d stores at most m key-value pairs from order, using O(m) space
• The sorted() function creates a new list containing all n characters from string s, using O(n) space
• The final string created by ''.join() also uses O(n) space, but this is the output and typically not counted in auxiliary space
• Overall auxiliary space: O(n + m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Default Value for Characters Not in Order

The Problem: The current solution uses 0 as the default value for characters not present in the order string. This places all such characters at the beginning of the result, which might not be the intended behavior. Many would expect these characters to appear at the end instead.

Example:

• order = "cba", s = "abcd"
• Current output: "dcba" (d comes first with priority 0)
• Expected by many: "cbad" (d comes last)

Solution: Use a large number (like len(order) or float('inf')) as the default value to place unordered characters at the end:

def customSortString(self, order: str, s: str) -> str:
    char_to_priority = {char: index for index, char in enumerate(order)}
    # Use len(order) to place unordered characters at the end
    sorted_chars = sorted(s, key=lambda char: char_to_priority.get(char, len(order)))
    return ''.join(sorted_chars)

Pitfall 2: Confusion About Relative Order of Unordered Characters

The Problem: When multiple characters from s don't appear in order, developers might assume these characters should maintain their original relative positions (stable sort), but with the same priority value, their relative order depends on Python's sort stability.

Example:

• order = "ab", s = "xyabz"
• With default value 0: outputs "xyzab" (x, y, z all get priority 0, maintain relative order)
• With default value at end: outputs "abxyz" (x, y, z all get same high priority)

Solution: If preserving the original order of unordered characters is important, use a two-tier sorting key:

def customSortString(self, order: str, s: str) -> str:
    char_to_priority = {char: index for index, char in enumerate(order)}
    # Two-tier key: (priority, original_index) to maintain stability
    indexed_s = [(char, i) for i, char in enumerate(s)]
    sorted_chars = sorted(indexed_s, 
                         key=lambda x: (char_to_priority.get(x[0], len(order)), x[1]))
    return ''.join(char for char, _ in sorted_chars)

Pitfall 3: Performance Optimization Opportunity Missed

The Problem: For cases where order contains most ASCII characters and s is very large, the sorting approach has O(n log n) complexity when a counting sort approach could achieve O(n).

Solution: Use a counting/bucket sort approach for better performance:

def customSortString(self, order: str, s: str) -> str:
    # Count frequency of each character in s
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
  
    result = []
    # Add characters in order
    for char in order:
        if char in char_count:
            result.append(char * char_count[char])
            del char_count[char]
  
    # Add remaining characters
    for char, count in char_count.items():
        result.append(char * count)
  
    return ''.join(result)

This approach has O(n + m) time complexity where n = len(s) and m = len(order).