Sort a String's Characters by a Given Character Order

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 bs come first, then the c, then the two as. 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"

Custom Order String Rearrangement

Hints

1. The alphabet has only 26 letters. What single pass over target tells you everything you need about the letters that appear in order?
2. Once you know how many times each listed letter occurs, walking order once lets you emit the whole first part of the answer.
3. Letters not in order must keep their original relative order, so collect them as you scan instead of sorting them.

Approach

Mark which letters appear in order using a 26-entry boolean table. Scan target once: for a listed letter, increment its count; for an unlisted letter, append it to a tail buffer, which preserves the unlisted letters' original relative order. Then walk order from left to right and emit each listed letter as many times as it was counted, which groups identical letters and places the groups by their position in order. Finally append the tail. Because identical letters are interchangeable and unlisted letters are kept in source order, this produces the one correct output. This is equivalent to a stable sort keyed by each letter's position in order (with unlisted letters sharing a key larger than every position), but counting avoids the O(n log n) comparison sort.

• Time complexity: O(n + m), where n = len(target) and m = len(order)
• Space complexity: O(n) for the output string (O(1) auxiliary beyond the output and the unlisted-tail buffer, which is itself bounded by n)