Log inSign up
mediumleetcodeNot Started

Custom Sort String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

Input: order = "cba", s = "abcd"
Output: "cbad"
Explanation: "c", "b", "a" appear in order, so the order of "c", "b", "a" should be "c", "b", and "a". Since "d" does not appear in order, it can be at any position in the returned string. "cbad", "dcba", "cdba", "cbda" are all valid outputs.

Example 2 · Example:

Input: order = "bcafg", s = "abcd"
Output: "bcad"
Explanation: "b", "c", "a" appear in order. "d" does not appear in order. So we place "b", then "c", then "a", and finally "d".

Constraints:

  • 1 <= order.length <= 26
  • 1 <= s.length <= 200
  • order and s consist of lowercase English letters.
  • All the characters of order are unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master custom ordering using counting sort principles over small alphabets.
  • Understand when comparator sorting is suboptimal compared to frequency bucket assembly.
  • Build clean and idiomatic multi-language implementations with string builders.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • When asked to sort elements according to a custom predefined priority list of size <= 26.
  • When remaining elements outside the priority list have no specific relative order requirements.

Algorithmic Decision Tree:

  • Counting Sort / Bucket Order
  • Custom Comparator

Connected Patterns:

Sort Characters By FrequencyRelative Sort ArrayTop K Frequent Words

1. Custom Comparator Sort

Intuition

Create a lookup array rank where rank[c] stores the 0-indexed position of character c in order. For any character not present in order, assign rank 26 (default infinity). Then convert string s to an array of characters and sort it comparing their mapped ranks.

When to apply: When code brevity is preferred or when alphabet size is large and dynamic.

Algorithm

  1. Initialize an array rank of size 26 with default value 26.
  2. For each character order[i], set rank[order[i] - 'a'] = i.
  3. Sort the characters of s using the comparator: rank[a - 'a'] - rank[b - 'a'].
  4. Join and return the sorted characters as a string.

Custom Comparator Sort

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, d]
Current operationSTEP 1 OF 6
Observation: Build priority map from order: 'c' is 0, 'b' is 1, 'a' is 2
Visual state
Values and pointers at this exact step
array
S
a
b
c
d
0
↑ Rank('a') = 2
1
↑ Rank('b') = 1
2
3
Variables at this step
order
cba
ranks
{"c":0,"b":1,"a":2,"default":26}
action
SWAP('a', 'b')
Check / comparison
order = 'cba': Rank('c')=0, Rank('b')=1, Rank('a')=2. Missing char rank = 26.
Decision / next transition
Compare 'a' and 'b': Rank('a')=2 > Rank('b')=1. Swap 'a' and 'b'.
Why this step matters

Observation: Build priority map from order: 'c' is 0, 'b' is 1, 'a' is 2.

Decision: Sort characters of s using custom comparator rank[a] - rank[b]. Since 'a' has higher rank (comes later) than 'b', swap them.

Invariant: Custom comparator ordering mirrors indices in order.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 std::string customSortString(std::string order, std::string s) {
9 std::vector<int> rank(26, 26);
10 for (int i = 0; i < (int)order.size(); ++i) {
11 rank[order[i] - 'a'] = i;
12 }
13 std::sort(s.begin(), s.end(), [&](char a, char b) {
14 return rank[a - 'a'] < rank[b - 'a'];
15 });
16 return s;
17 }
18};
19
20int main() {
21 Solution sol;
22 std::cout << sol.customSortString("cba", "abcd") << std::endl; // "cbad"
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting an N-length string with comparison sort takes O(N log N) time.
  • Space complexity: O(N) for character conversion array / comparator stack

Why Brute Force Doesn't Scale:

Counting frequencies via a 26-size array eliminates sorting comparisons entirely.

Pre-allocating a StringBuilder/string buffer of size s.length prevents reallocation during construction.

2. Hash Map Frequency Accumulator

Intuition

Build a hash map storing the occurrence count of each character in s. Iterate through each character in order: if it exists in the map, append it to the result as many times as its count, then delete that key from the map. Finally, iterate through all remaining keys in the map and append them.

When to apply: When dealing with arbitrary Unicode characters or large non-contiguous alphabet sets.

Algorithm

  1. Create a hash map countMap of character counts in s.
  2. For each character ch in order, if countMap has ch, append ch countMap[ch] times to result and remove ch.
  3. For each remaining (key, count) in countMap, append key count times.
  4. Return the accumulated result string.

Hash Map Frequency Accumulator

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, d]
Current operationSTEP 1 OF 6
Observation: Iterate over s = 'abcd' to count occurrences of every character
Visual state
Values and pointers at this exact step
array
S
a
b
c
d
0
↑ BUILD FREQ MAP
1
2
3
Variables at this step
map
{"a":1,"b":1,"c":1,"d":1}
result
Check / comparison
Scan s = 'abcd' and populate frequency map.
Decision / next transition
Map: { a: 1, b: 1, c: 1, d: 1 }.
Why this step matters

Observation: Iterate over s = 'abcd' to count occurrences of every character.

Decision: Store counts in hash map: { a:1, b:1, c:1, d:1 }.

Invariant: Frequency map captures character multiplicities without modifying input string.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5class Solution {
6public:
7 std::string customSortString(std::string order, std::string s) {
8 std::unordered_map<char, int> freq;
9 for (char c : s) freq[c]++;
10
11 std::string result = "";
12 for (char c : order) {
13 if (freq.count(c)) {
14 result.append(freq[c], c);
15 freq.erase(c);
16 }
17 }
18 for (auto& [c, count] : freq) {
19 result.append(count, c);
20 }
21 return result;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.customSortString("bcafg", "abcd") << std::endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(order.length + s.length) — Populating the map takes O(N), querying order takes O(M), and remaining drain takes O(K).
  • Space complexity: O(K) where K is unique character count in s

3. Fixed 26-Element Frequency Array (Counting Sort)

Intuition

Using a fixed array of size 26 avoids hashing overhead and memory fragmentation. First, count all characters in s. Next, iterate over order and append order[i] as many times as its count in the array, then zero out the count. Finally, iterate through indices 0 to 25 and append any characters with remaining non-zero counts.

When to apply: Optimal standard for fixed lowercase English alphabet constraints.

Algorithm

  1. Initialize int count[26] = {0}.
  2. Iterate through s and increment count[c - 'a'] for each character.
  3. Iterate through order: for character c, append c count[c - 'a'] times to the string builder and set count[c - 'a'] = 0.
  4. Loop from i = 0 to 25: if count[i] > 0, append (char)('a' + i) count[i] times.
  5. Return the constructed string.

Order-Priority Bucket Frequency Reconstruction

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, d]
Current operationSTEP 1 OF 6
Observation: Count frequency of every character in s: { a: 1, b: 1, c: 1, d: 1 }
Visual state
Values and pointers at this exact step
array
S
a
b
c
d
0
↑ Tally frequencies in s
1
2
3
Variables at this step
counts
{"a":1,"b":1,"c":1,"d":1}
order
cba
result
Why this step matters

Observation: Count frequency of every character in s: { a: 1, b: 1, c: 1, d: 1 }.

Decision: Iterate through order = "cba" to append characters according to custom priority.

Invariant: Priority order characters must appear before any unlisted characters.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string customSortString(std::string order, std::string s) {
8 int count[26] = {0};
9 for (char c : s) {
10 count[c - 'a']++;
11 }
12
13 std::string result = "";
14 result.reserve(s.size());
15
16 for (char c : order) {
17 while (count[c - 'a'] > 0) {
18 result.push_back(c);
19 count[c - 'a']--;
20 }
21 }
22
23 for (int i = 0; i < 26; ++i) {
24 while (count[i] > 0) {
25 result.push_back((char)('a' + i));
26 count[i]--;
27 }
28 }
29
30 return result;
31 }
32};
33
34int main() {
35 Solution sol;
36 std::cout << sol.customSortString("cba", "abcd") << std::endl; // "cbad"
37 std::cout << sol.customSortString("bcafg", "abcd") << std::endl; // "bcad"
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(order.length + s.length) — Scanning s takes O(N), traversing order takes O(M <= 26), and scanning remaining 26 elements is O(1).
  • Space complexity: O(1) auxiliary space (26-element array)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Custom Comparator SortO(N log N)O(1) auxiliarySimple and intuitive to write using built-in sort functions.Log-linear time due to sorting comparison overhead.
2.Frequency Map / Counting ArrayO(M + N)O(1) (fixed 26-element array)Linear time O(M + N), optimal performance, minimal memory.Requires two passes (one for defined order, one for remainder).
3.Optimal Direct Frequency Bucket ConstructionOptimalO(order.length + s.length)O(1) extra spaceDirect building via string builders, zero dynamic allocations, strictly linear.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Overwriting characters or forgetting remaining characters not in order.

Pitfall 2:

String concatenation inside tight loops instead of string builder causing O(N2) memory copies.

Crucial Edge Cases to Validate:

  • No common characters between order and s: Order characters will have count 0 and skipped; all characters from s will be appended during leftover phase.
  • s contains multiple duplicate characters: The while loop appends each character as many times as its recorded frequency.
  • s.length == 1 or order.length == 1: Handled seamlessly with exact one pass.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the counting sort intuition right away: since alphabet size is bounded by 26, counting frequencies yields an optimal O(M + N) solution.
  2. Mention string builder pre-allocation to showcase attention to memory optimization.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the counting sort approach faster than standard comparator sort for this problem?

Back to DSA Sheet