Waymo: Sort a String's Characters by a Given Character Order

Quick Overview

Rearrange the characters of a target string so they follow the order given by a second string, placing characters not in that order at the end in their original relative order. Tests custom sort keys, counting, and stable handling of unranked characters.

You are given two strings, target and order. Rearrange the characters of target so that they are sorted according to order: a character that appears earlier in order must come before a character that appears later in order. Return the rearranged string.

Function Signature

def sort_by_order(target: str, order: str) -> str:

Rules

The result contains exactly the characters of target , each as many times as it occurs in target .
Characters of target that appear in order come first, grouped and arranged by their position in order .
Characters of target that do not appear in order come after all of those, in the same relative order in which they appear in target .
order contains no repeated characters. It may contain characters that do not occur in target , and it may be empty.

Constraints

0 <= len(target) <= 10^5
0 <= len(order) <= 26
Both strings contain only lowercase English letters a to z .

Examples

Example 1

Input: target = "cabbage" , order = "bca"
Output: "bbcaage"
Explanation: The two b s come first, then the c , then the two a s. g and e are not in order , so they follow in the order they appear in target .

Example 2

Input: target = "sensor" , order = "nrx"
Output: "nrseso"
Explanation: n then r come first; x does not occur in target . The remaining characters s , e , s , o keep their original relative order.

Example 3

Input: target = "abc" , order = ""
Output: "abc"

Sort a String's Characters by a Given Character Order