Sort a String's Characters by a Given Character Order
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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"`
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.
Implement `sort_by_order(target, order)`.
### 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.
These rules fix exactly one correct output for every valid input: identical letters are interchangeable, listed letters are placed by their position in `order`, and unlisted letters keep their original relative order.
### Constraints
- `0 <= len(target) <= 10^5`
- `0 <= len(order) <= 26`
- Both strings contain only lowercase English letters `a` to `z`.
- `order` contains no repeated characters.
### 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"`
Constraints
- 0 <= len(target) <= 10^5
- 0 <= len(order) <= 26
- Both strings contain only lowercase English letters a to z.
- order contains no repeated characters; it may be empty and may contain letters that do not occur in target.
Examples
Input: ('cabbage', 'bca')
Expected Output: "bbcaage"
Explanation: Example 1.
Input: ('sensor', 'nrx')
Expected Output: "nrseso"
Explanation: Example 2: 'x' is listed but absent from target.
Hints
- The alphabet has only 26 letters. What single pass over target tells you everything you need about the letters that appear in order?
- Once you know how many times each listed letter occurs, walking order once lets you emit the whole first part of the answer.
- Letters not in order must keep their original relative order, so collect them as you scan instead of sorting them.
Community answers
Answer by fijeijfakdknjkvl
def sort_by_order(target: str, order: str) -> str:
count = {}
for char in target:
count[char] = count.get(char, 0) + 1
result = []
for char in order:
if char in count:
result.append(char * count[char])
del count[char]
# add the leftover characters in original order
for char in target:
if char in count:
result.append(char)
return ''.join(result)