Custom Sort String
Rearrange a string so its letters follow a custom alphabet order. A counting problem that shows when a full comparison sort is more than you need. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given two strings. order lists some lowercase letters, each at most once, in a custom priority. s is any lowercase string.
Rearrange the characters of s so that letters appearing in order come first, in the same relative order they have in order. If x comes before y in order, every x in the result must come before every y.
Characters of s that don't appear in order go after all the ordered ones, and they keep their original relative order from s. That rule makes the answer unique.
Example 1
- Input
- order = "dog", s = "goodday"
- Output
- "ddoogay"
The two d's, then the two o's, then g. The leftovers a and y keep the order they had in s.
Example 2
- Input
- order = "zyx", s = "xyz"
- Output
- "zyx"
Example 3
- Input
- order = "q", s = "banana"
- Output
- "banana"
No letter of s is in order, so everything stays where it was.
Constraints
- 1 ≤ order.length ≤ 26
- 1 ≤ s.length ≤ 10⁵
- order and s contain only lowercase English letters.
- All characters of order are distinct.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Custom Sort String in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Custom Sort String
Pattern: Counting sort by a custom key
"Sort by a custom order" suggests a comparator, but the alphabet has only 26 letters. You don't need to compare characters at all: count how many of each letter s contains, then write them out in the sequence order gives.
The letters that are not in order are the only part that needs care. Walk s once more and append each of them as you meet it, which keeps their original relative order.
Approach 1: Stable sort with a rank key
Give each letter in order its index as a rank and every other letter rank 26. A stable sort of s by rank produces exactly the required answer, because ties (all the unranked letters) keep their input order.
Time O(n log n) · Space O(n)
Approach 2: Count, then emit in order
- Count every character of
s. - For each letter of
order, append it as many times as it was counted. - Walk
sagain and append each character that is not inorder, in place.
Each character is touched a constant number of times.
Time O(n + |order|) · Space O(n) for the output, O(1) for the counts
| Approach | Time | Space |
|---|---|---|
| Stable sort with a rank key | O(n log n) | O(n) |
| Count, then emit in order | O(n + |order|) | O(n) for the output, O(1) for the counts |
Solution code
Try the practice editor first. Both solutions pass every test above.
Custom Sort String solution in Python
from collections import Counter
def custom_sort_string(order: str, s: str) -> str:
counts = Counter(s)
parts = [c * counts[c] for c in order]
in_order = set(order)
parts.extend(c for c in s if c not in in_order)
return "".join(parts)Custom Sort String solution in JavaScript
function customSortString(order, s) {
const counts = new Map();
for (const c of s) counts.set(c, (counts.get(c) ?? 0) + 1);
const parts = [];
for (const c of order) parts.push(c.repeat(counts.get(c) ?? 0));
const inOrder = new Set(order);
for (const c of s) if (!inOrder.has(c)) parts.push(c);
return parts.join('');
}Common mistakes
- Appending the leftover letters grouped by letter (all a's, then all b's), which breaks their original order.
- Using an unstable sort with the rank key, which can shuffle the unranked letters.
- Forgetting letters of `order` that do not appear in `s` and emitting them anyway.
- Building the result with repeated string concatenation in a loop in a language where that is quadratic. Collect pieces and join once.
What interviewers look for
Mention the comparator approach first because it is the obvious one, then point out that a 26-letter alphabet means counting beats sorting. Interviewers like hearing you notice a small fixed key space.
Call out the tie rule for unlisted letters explicitly and show how your code honours it. If the interviewer says any order is fine for them, note that your version still works and is just one valid answer.
Follow-up questions
What if the alphabet were all of Unicode instead of 26 letters?
Use a hash map for the counts and a hash map from character to rank. The counting approach still runs in O(n + |order|); only the constant changes.
How would you check whether a string already follows the custom order?
Map each character in `order` to its rank, then scan the string and make sure the ranks of ranked characters never decrease. This is the "verify an alien dictionary" idea in a simpler form.
What if you had to sort a list of words, not characters, by the custom alphabet?
Translate each word into a tuple of ranks (or map each letter to the letter at that rank in the normal alphabet) and sort by that key. Comparison is now needed, so it costs O(total length · log n).
Companies that ask Custom Sort String
Custom Sort String is tagged by 74 companies in our interview dataset. The score shows how often it comes up at each company.
- Sentinelone100%
- Bandwidth98%
- Harman International96%
- Ikea96%
- Checkoutcom95%
- Improbable93%
- Alation92%
- Costar Group92%
- Biomérieux90%
- Oscar Health85%
- Nbc84%
- Epic Games83%
- Fiserv81%
- Nebius80%
- Zoominfo78%
- Pegasystems78%
- Allstate78%
- Twist Bioscience75%
- Sortly74%
- C3.ai73%
- Ihs Markit73%
- Meta72.8%
- Gft Group72%
- Boston Scientific71%
and 50 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required