#791

Medium

LeetCode Problem Workspace

Custom Sort String

Sort the string `s` according to a custom order defined by string `order`.

Problem Statement

You are given two strings order and s. The string order consists of unique lowercase letters and defines a custom sorting order. The task is to rearrange the characters of string s so that characters from order appear in the specified order, while the remaining characters (not in order) can be positioned freely.

Return any valid permutation of s that satisfies this condition. If a character x appears before y in order, then in the resulting string, x must appear before y. Characters not in order can be placed at any position.

Examples

Example 1

Input: order = "cba", s = "abcd"

Output: "cbad"

"a" , "b" , "c" appear in order, so the order of "a" , "b" , "c" should be "c" , "b" , and "a" . Since "d" does not appear in order , it can be at any position in the returned string. "dcba" , "cdba" , "cbda" are also valid outputs.

Example 2

Input: order = "bcafg", s = "abcd"

Output: "bcad"

The characters "b" , "c" , and "a" from order dictate the order for the characters in s . The character "d" in s does not appear in order , so its position is flexible. Following the order of appearance in order , "b" , "c" , and "a" from s should be arranged as "b" , "c" , "a" . "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "dbca" or "bcda" would also be valid, as long as "b" , "c" , "a" maintain their order.

Constraints

1 <= order.length <= 26
1 <= s.length <= 200
order and s consist of lowercase English letters.
All the characters of order are unique.

Solution Approach

Mapping characters using a hash table

Create a hash table to store the index of each character from the custom order string order. This allows quick lookup and comparison while sorting.

Sorting based on custom order

Sort the characters of s using the hash table to determine their order, while preserving the relative positions of characters not included in order.

Placing remaining characters

After sorting characters based on order, place all remaining characters (those not found in order) at any available position in the result string.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity of this solution is O(N), where N is the length of the string s. The space complexity is O(N) due to the use of the hash table to store the character positions in order.

What Interviewers Usually Probe

Ability to handle custom sorting logic efficiently.
Understanding of how hash tables can be used for fast lookups.
Clarity in explaining sorting and how to handle characters not in the custom order.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling characters not in the custom order by placing them in fixed positions.
Failing to consider that only characters in order should be ordered, and others can appear in any arrangement.
Overcomplicating the problem by attempting to sort non-existent or non-required elements.

Follow-up variants

Using a more complex sorting algorithm instead of hash table-based indexing.
Implementing this solution with more constraints, such as additional characters or mixed order sets.
Handling non-lowercase characters, which may change how the hash table and sorting logic are implemented.

FAQ

What is the best approach to solve the Custom Sort String problem?

The optimal solution uses a hash table to store the custom order and applies it to sort string s efficiently.

What are the time and space complexities for Custom Sort String?

Time complexity is O(N) and space complexity is O(N), where N is the length of the input string s.

How do I handle characters not in the custom order in Custom Sort String?

Characters not found in order can be placed anywhere in the result string after sorting the characters from order.

What is the key to solving the Custom Sort String problem efficiently?

Efficiently solving the problem relies on using a hash table for quick lookup and sorting based on that table.

Can multiple valid outputs exist for the Custom Sort String problem?

Yes, multiple valid outputs are possible as long as the order of characters in s respects the custom order from order.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        d = {c: i for i, c in enumerate(order)}
        return ''.join(sorted(s, key=lambda x: d.get(x, 0)))

Solution 2

#### Python3

1

2

3

4

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        d = {c: i for i, c in enumerate(order)}
        return ''.join(sorted(s, key=lambda x: d.get(x, 0)))

Continue Practicing

#792 number of matching subsequences #767 reorganize string #833 find and replace in string