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 <= 200order and s consist of lowercase English letters.order are unique.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.
C++
Java
Python
C#
JavaScript
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.
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.
Java
Python
JavaScript
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 | 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. |
CUSTOM SORT STRING | PYTHON | LEETCODE # 791 • Cracking FAANG • 7,656 views views
Watch 9 more video solutions →Practice Custom Sort String with our built-in code editor and test cases.
Practice on FleetCode