Custom Sort String — Solution in Python, Java & C++
Custom Sort String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Custom Sort String is a medium coding problem on strings, hash table and sorting, asked in Amazon, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sorting
- Asked at: Amazon, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings, order and s. The characters of order are distinct and were sorted into a custom order.
Permute s so that characters appearing in order come first, grouped and arranged in exactly that order. Characters of s that do not appear in order follow, keeping their original relative order.
Example 1
Input: order = "cba", s = "abcd"
Output: cbad
Explanation: c, b and a follow the custom order; d is not in order, so it keeps its place at the end.
Example 2
Input: order = "bcafg", s = "abcd"
Output: bcad
Example 3
Input: order = "xyz", s = "abc"
Output: abc
Explanation: Nothing in s appears in order, so s is unchanged.
Constraints
1 <= order.length <= 261 <= s.length <= 40Both consist of lowercase English letters.The characters of order are distinct.
Hints for Custom Sort String
Hint 1
Count the letters of
s; the answer needs the multiplicities, not the positions.Hint 2
Walk
orderand emit each of its letters as many times asscontains it.Hint 3
Then walk
sonce more and emit only the letters thatordernever mentioned — that pass is what preserves their relative order.
How to solve Custom Sort String
Only multiplicities matter for the ordered part: count s, emit each letter of order as many times as counted, then append the remaining letters of s in their original order.
Approach
- Count the characters of
s. - For each character of
order, append itcounttimes and remove it from the map. - Walk
sonce more, appending only characters still in the map.
Why it works
Grouping all copies of each ordered letter is exactly what the custom order requires, and the second pass over s — not over the map — is what preserves the relative order of the leftovers.
Complexity
- Time —
O(n + m) - Space —
O(n)
Pitfalls
- Emitting leftovers from the map iterates in hash order and loses their original sequence.
orderhas distinct characters, so each is processed once.
Reference solution
Python
def customSortString(order: str, s: str) -> str:
count = {}
for ch in s:
count[ch] = count.get(ch, 0) + 1
parts = []
for ch in order:
if ch in count:
parts.append(ch * count[ch])
del count[ch]
for ch in s:
if ch in count:
parts.append(ch)
return "".join(parts)Java
public static String customSortString(String order, String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
boolean[] used = new boolean[26];
StringBuilder out = new StringBuilder();
for (int i = 0; i < order.length(); i++) {
int idx = order.charAt(i) - 'a';
for (int r = 0; r < count[idx]; r++) out.append(order.charAt(i));
used[idx] = true;
}
for (int i = 0; i < s.length(); i++) {
if (!used[s.charAt(i) - 'a']) out.append(s.charAt(i));
}
return out.toString();
}C++
string customSortString(string order, string s) {
int count[26] = {0};
for (char c : s) count[c - 'a']++;
bool used[26] = {false};
string out = "";
for (char c : order) {
for (int r = 0; r < count[c - 'a']; r++) out += c;
used[c - 'a'] = true;
}
for (char c : s) {
if (!used[c - 'a']) out += c;
}
return out;
}JavaScript
var customSortString = function(order, s) {
const count = new Map();
for (let i = 0; i < s.length; i++) {
count.set(s[i], (count.get(s[i]) || 0) + 1);
}
let out = "";
for (let i = 0; i < order.length; i++) {
const c = count.get(order[i]);
if (c) {
for (let k = 0; k < c; k++) out += order[i];
count.delete(order[i]);
}
}
for (let i = 0; i < s.length; i++) {
if (count.has(s[i])) out += s[i];
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets