Custom Sort String - Solution & Explanation
Problem Statement
You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation of s that satisfies this property.
Example 1:
Input: order = "cba", s = "abcd"
Output: "cbad"
Explanation: "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"
Explanation: 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 <= 261 <= s.length <= 200orderandsconsist of lowercase English letters.- All the characters of
orderare unique.
Approach Overview
Problem Overview: You receive two strings: order and s. The characters in order define the required priority. Rearrange characters in s so they follow this custom order. Characters not present in order can appear anywhere after the ordered ones.
Approach 1: Counting Sort with Frequency Map (O(n + m) time, O(1) space)
This approach treats the problem like a constrained counting sort. First build a frequency table for characters in s using a simple array or hash table. Then iterate through each character in order and append it to the result as many times as its frequency indicates. After processing all characters in order, append the remaining characters from the frequency map that were not specified in the custom order.
The key insight is that you never need to compare characters directly. The custom order already defines the sequence. Counting occurrences lets you reconstruct the string in linear time. Because the alphabet size is fixed (typically 26 lowercase letters), the extra memory is constant. This method is essentially a specialized form of sorting optimized for character frequencies.
Approach 2: Sorting with Custom Comparator (O(n log n) time, O(n) space)
This approach leverages a standard sorting algorithm but modifies how characters are compared. First build a lookup table that maps each character in order to its index. Then convert the string s into a list and sort it using a custom comparator or key function. During comparison, characters with lower order indices come first. Characters not present in order can be assigned a default large index so they naturally move to the end.
This method uses built-in sorting utilities and keeps the implementation straightforward. The algorithm repeatedly compares characters using the custom ranking, which leads to O(n log n) time complexity. It relies on concepts from string manipulation and custom sorting logic. The approach is useful when adapting to problems where frequency counting is not feasible or when the ordering rule becomes more complex.
Recommended for interviews: The counting sort approach is the expected solution. It achieves linear time by avoiding comparisons and directly reconstructing the result using frequency counts. Interviewers often accept the comparator-based solution first since it demonstrates understanding of custom sorting, but the counting strategy shows stronger algorithmic optimization and awareness of fixed character constraints.
Approach 1: Counting Sort Approach
This approach involves counting the occurrence of each character in string s and then constructing the result string by iterating through characters in order, followed by any characters in s that do not appear in order. This ensures the output string follows the custom order defined.
The solution uses a frequency array to count occurrences of characters in string s. Next, it iterates through the custom order string order to construct part of the result by taking corresponding characters from s. Finally, any leftover characters from s are added to the result in their natural order.
Complexity
Time Complexity: O(n + m), where n is the length of s and m is the length of order, since we iterate through each character of both strings.
Space Complexity: O(1), only a fixed extra space for the frequency array is used.
Approach 2: Sorting with Custom Comparator
This approach involves sorting the string s using a custom comparator function derived from the order string. You respect the sequence provided in order and sort the characters of s accordingly.
In this C++ solution, an unordered_map is used to assign indices as priorities based on order. The custom comparator used in the sort function rearranges s to fit these priorities.
Code
C++
Java
Python
JavaScript
Complexity
Time Complexity: O(n log n), due to the sorting operation.
Space Complexity: O(1) for map usage and additional space for sort function.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Counting Sort Approach | Time Complexity: O(n + m), where n is the length of |
| Sorting with Custom Comparator | Time Complexity: O(n log n), due to the sorting operation. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Sort with Frequency Map | O(n + m) | O(1) | Best general solution when characters come from a limited alphabet |
| Sorting with Custom Comparator | O(n log n) | O(n) | Useful when relying on built-in sorting or when ordering rules are more flexible |
Video Solution
CUSTOM SORT STRING | PYTHON | LEETCODE # 791 • Cracking FAANG • 9,074 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Custom Sort String easy or hard?
Custom Sort String Python/Java solution
How to solve Custom Sort String in O(n)?
What is the best approach for Custom Sort String?
Is Custom Sort String asked at Google/Amazon/Meta?
What data structure is used in Custom Sort String?
What is the time complexity of Custom Sort String?
Ready to solve this problem?
Practice Custom Sort String with our built-in code editor and test cases.
Practice on FleetCode