Custom Sort String

Custom Sort String looks odd the first time you read it. You do not sort by A to Z. You sort by a rule that someone else gives you. So the interviewer wants to see if you can follow a custom order instead of the normal one. That small twist trips up a lot of people.

🎯 The Problem

You get two strings and you rearrange the second to match the order set by the first.

• You get a string called order. It lists letters in the exact order you must follow.
• You get a string called s. You rearrange its letters to match order.
• A letter in s that is not in order can go anywhere. We place it at the end.
• We call this a priority order, because each letter’s place comes from the order string.

For order = "cba" and s = "abcd": c comes first, then b, then a. The letter d is not in order, so it goes last. The answer is "cbad".

Input:  order = "cba", s = "abcd"
Output: "cbad"

Explanation: c, b, a follow the order string. d is not listed, so it goes last.

Here is the rule drawn out. Each letter in s looks up its place in order.

🐢 Approach 1: Sort With a Comparator (Brute Force)

Sort the letters of s, but by their place in order instead of A to Z.

The idea:

• Give the sort a comparator. That is the rule the sort uses to decide which letter comes first.
• The rule: a letter’s position in order is its rank.
• A letter not in order gets a large rank, so it lands at the end.

How it works:

• For every pair of letters, look up both ranks in order.
• The smaller rank comes first.

Why it is weak:

• A sort compares letters again and again.
• Every compare does a lookup in order.
• Time grows as O(n log n), where n is the length of s.

Here is the comparator-style code for that idea:

def custom_sort_string(order, s):
    rank = {ch: i for i, ch in enumerate(order)}
    return "".join(sorted(s, key=lambda ch: rank.get(ch, len(order))))

⚡ Approach 2: Counting Sort (Best)

The idea in one line: we never compare letters, we just count them and rebuild.

The idea:

• We only need how many times each letter appears in s.
• Then we walk order and add each letter that many times.
• This is a counting sort. It builds the answer from counts, not compares.

How it works:

• Count every letter in s into a small table of 26 slots.
• Walk order one letter at a time. Add each letter as many times as its count.
• Add the leftovers last. Those are letters in s that were never in order.

Why it is fast:

• No comparisons at all. We only read counts.
• One pass to count, one pass to build. So O(n) time.

Here is a dry run of the counting approach on the example.

Steps to Solve

1. Count how many times each letter appears in s. Store the counts in a small table.
2. Create an empty result.
3. Walk through order one letter at a time.
4. For each letter in order, add it to the result that many times, then set its count to zero.
5. After order is done, walk through the table again and add any letter that still has a count left.
6. Join everything into the final string and return it.

#include <stdio.h>
#include <string.h>

void customSort(const char *order, const char *s, char *out) {
    int count[26] = {0};       // count of each letter in s
    for (int i = 0; s[i]; i++) {
        count[s[i] - 'a']++;   // tally the letter
    }
    int pos = 0;
    for (int i = 0; order[i]; i++) {       // follow the custom order
        int c = order[i] - 'a';
        while (count[c] > 0) {             // add this letter that many times
            out[pos++] = order[i];
            count[c]--;
        }
    }
    for (int c = 0; c < 26; c++) {         // add leftover letters
        while (count[c] > 0) {
            out[pos++] = 'a' + c;
            count[c]--;
        }
    }
    out[pos] = '\0';
}

int main(void) {
    char out[100];
    customSort("cba", "abcd", out);
    printf("%s\n", out);
    return 0;
}

cbad

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string customSort(string order, string s) {
    vector<int> count(26, 0);          // count of each letter in s
    for (char ch : s) count[ch - 'a']++;
    string result = "";
    for (char ch : order) {            // follow the custom order
        while (count[ch - 'a'] > 0) {
            result += ch;
            count[ch - 'a']--;
        }
    }
    for (int c = 0; c < 26; c++) {     // add leftover letters
        while (count[c] > 0) {
            result += (char)('a' + c);
            count[c]--;
        }
    }
    return result;
}

int main() {
    cout << customSort("cba", "abcd") << endl;
    return 0;
}

cbad

public class CustomSortString {
    public static String customSort(String order, String s) {
        int[] count = new int[26];          // count of each letter in s
        for (char ch : s.toCharArray()) count[ch - 'a']++;
        StringBuilder result = new StringBuilder();
        for (char ch : order.toCharArray()) {   // follow the custom order
            while (count[ch - 'a'] > 0) {
                result.append(ch);
                count[ch - 'a']--;
            }
        }
        for (int c = 0; c < 26; c++) {          // add leftover letters
            while (count[c] > 0) {
                result.append((char) ('a' + c));
                count[c]--;
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(customSort("cba", "abcd"));
    }
}

cbad

from collections import Counter


def custom_sort(order, s):
    count = Counter(s)          # number -> count of each letter in s
    result = []
    for ch in order:            # follow the custom order
        result.append(ch * count[ch])   # add ch that many times
        count[ch] = 0           # mark it as used
    for ch, c in count.items(): # add leftover letters
        result.append(ch * c)
    return "".join(result)


print(custom_sort("cba", "abcd"))

cbad

function customSort(order, s) {
  const count = new Map(); // letter -> count in s
  for (const ch of s) {
    count.set(ch, (count.get(ch) || 0) + 1);
  }
  let result = "";
  for (const ch of order) {        // follow the custom order
    if (count.has(ch)) {
      result += ch.repeat(count.get(ch)); // add ch that many times
      count.set(ch, 0);            // mark it as used
    }
  }
  for (const [ch, c] of count) {   // add leftover letters
    result += ch.repeat(c);
  }
  return result;
}

console.log(customSort("cba", "abcd"));

cbad

Let us walk through the Python version line by line, because it shows the idea most clearly.

count = Counter(s) builds a table of how many times each letter shows up in s. For "abcd" every letter has a count of one. We start here because counting once lets us skip all the comparing later.

for ch in order: walks through the order string. This is what makes the sort custom. We do not go A to Z. We go in the exact order the problem gave us.

result.append(ch * count[ch]) adds that letter as many times as it appeared. In Python ch * 2 gives "cc". So if a letter appeared twice, we add two copies in one move.

count[ch] = 0 marks the letter as done. This matters. It stops us from adding the same letter again in the leftover step.

for ch, c in count.items(): handles the leftovers. These are letters that were in s but never in order, like d. They still have a count, so we add them now. They land at the end, which is exactly the rule.

return "".join(result) glues all the pieces into one final string. We built a list first and joined at the end because joining once is faster than adding to a string over and over.

⏱️ Time and Space Complexity

The comparator sort is fine but it compares letters again and again, so it costs O(n log n) time. The counting sort skips all comparisons. It counts once, then reads the counts, so it runs in O(n) time. Both need a small fixed table of 26 counts, so the extra space is tiny. That makes counting the clear winner, since it drops the time to O(n) for almost no extra cost.

🧩 Key Takeaways

• ✅ You sort by a custom order, not by A to Z. Each letter’s place comes from the order string.
• ✅ Counting how many times each letter appears lets you skip all the comparing.
• ✅ Walk through order and add each letter as many times as its count.
• ✅ Letters not in order still appear in the answer. Add them at the end.
• ✅ Counting sort runs in O(n) time, faster than the O(n log n) comparator sort.

🚀 What’s Next?

• Valid Word Abbreviation
• Minimum Remove to Make Valid Parentheses