Custom Sort String
Medium · Arrays & Hashing · Hash Table · String · Sorting · Counting
Problem
You are given two strings order and s. The letters of order are all different and define a custom ranking: a letter that appears earlier in order ranks earlier.
Return a rearrangement of s that respects this ranking: if x comes before y in order, every x in the result must come before every y. Letters of s that do not appear in order may go anywhere.
Any rearrangement that follows these rules is accepted.
Examples
Input: order = "zyx", s = "xxyaz" Output: "zyxxa"
z, then y, then both x's. The unranked a may go anywhere, so "azyxx" or "zyaxx" are accepted too.
Input: order = "ab", s = "bba" Output: "abb"
a must come before both b's, and this is the only valid answer.
Input: order = "q", s = "cat" Output: "cat"
No letter of s is ranked, so every rearrangement of s is valid.
Constraints
- 1 <= len(order) <= 26
- 1 <= len(s) <= 200
- order and s consist of lowercase English letters
- all letters of order are different
Approaches
- Sort by rank — time O(n log n), space O(n)
Follow-up
What if order ranked whole words and you had to sort a list of words in that dictionary? Translate each word into the list of its letters' ranks and sort by that key: list comparison handles the prefix rule for free.
Related problems
Start free on Cariara · Coding problems · System design studio
