Custom Sort String

Problem Statement

Given a string order listing a custom priority of characters, and a string s, return s rearranged so its characters follow order. Characters not in order may go anywhere (typically last).

Example

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

Approach

Build a rank map from each character in order to its index. Sort the characters of s by that rank; characters missing from order get a large default rank so they trail. A counting-based variant runs in O(n).

Complexity

• Time: O(n log n) (O(n) with counting)
• Space: O(n)

Solution Code

Python

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

Java

String customSortString(String order, String s) {
    int[] rank = new int[26];
    Arrays.fill(rank, 26);
    for (int i = 0; i < order.length(); i++) rank[order.charAt(i) - 'a'] = i;
    Character[] chars = new Character[s.length()];
    for (int i = 0; i < s.length(); i++) chars[i] = s.charAt(i);
    Arrays.sort(chars, (a, b) -> rank[a - 'a'] - rank[b - 'a']);
    StringBuilder sb = new StringBuilder();
    for (char c : chars) sb.append(c);
    return sb.toString();
}

C++

string customSortString(string order, string s) {
    int rank[26];
    for (int i = 0; i < 26; i++) rank[i] = 26;
    for (int i = 0; i < (int)order.size(); i++) rank[order[i] - 'a'] = i;
    sort(s.begin(), s.end(),
         [&](char a, char b){ return rank[a - 'a'] < rank[b - 'a']; });
    return s;
}

Key Takeaways

• A rank map turns a custom priority into a numeric sort key.
• Give unlisted characters a large default rank so they sort to the end.
• Reference: LeetCode 791 (Custom Sort String).