Custom Sort String

Medium
232.

Custom Sort String

Custom Sort String is a medium coding problem on strings, hash table and sorting, asked in Amazon, Meta and Bloomberg interviews.

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 <= 26
  • 1 <= s.length <= 40
  • Both consist of lowercase English letters.
  • The characters of order are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} order
 * @param {string} s
 * @return {string}
 */
var customSortString = function(order, s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 26
  • 1 <= s.length <= 40
  • Both consist of lowercase English letters.
  • The characters of order are distinct.

Hints for Custom Sort String

  1. Hint 1

    Count the letters of s; the answer needs the multiplicities, not the positions.

  2. Hint 2

    Walk order and emit each of its letters as many times as s contains it.

  3. Hint 3

    Then walk s once more and emit only the letters that order never 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

  1. Count the characters of s.
  2. For each character of order, append it count times and remove it from the map.
  3. Walk s once 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.
  • order has 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