# LeetCode 791: Custom Sort String

## Problem Restatement

We are given two strings:

```python
order
s
```

All characters in `order` are unique.

The string `order` defines a custom ordering of characters. We need to rearrange the characters of `s` so that characters appearing in `order` follow that same relative order.

Characters in `s` that do not appear in `order` may be placed anywhere in the result.

Return any valid permutation of `s`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Strings `order` and `s` |
| Output | Any permutation of `s` that respects `order` |
| Custom rule | If `x` appears before `y` in `order`, then all `x`s must appear before all `y`s in the result |
| Extra characters | Characters not in `order` can go anywhere |
| Characters | Lowercase English letters |

Function shape:

```python
class Solution:
    def customSortString(self, order: str, s: str) -> str:
        ...
```

## Examples

Example 1:

```python
order = "cba"
s = "abcd"
```

The custom order says:

```text
c before b before a
```

The character `d` does not appear in `order`, so it can be placed anywhere.

One valid answer is:

```python
"cbad"
```

Other valid answers include:

```python
"dcba"
"cdba"
"cbda"
```

Example 2:

```python
order = "bcafg"
s = "abcd"
```

The characters from `s` that appear in `order` are:

```text
b, c, a
```

They must appear in that order.

The character `d` is not in `order`, so it can be placed anywhere.

One valid answer is:

```python
"bcad"
```

## First Thought: Sort With a Custom Rank

One direct solution is to assign every character in `order` a rank.

For example:

```python
order = "cba"
```

gives:

| Character | Rank |
|---|---:|
| `c` | `0` |
| `b` | `1` |
| `a` | `2` |

Then we sort the characters of `s` by this rank.

Characters not in `order` can receive any default rank, because their position is flexible.

This works, but sorting costs `O(n log n)`.

Since the alphabet is small and lowercase, we can do better with counting.

## Key Insight

We do not need comparison sorting.

We only need to place characters from `s` in the order given by `order`.

So we can:

1. Count how many times each character appears in `s`.
2. Append characters that appear in `order`, following `order`.
3. Append remaining characters that were not in `order`.

This is a counting-sort style solution.

## Algorithm

1. Count all characters in `s`.
2. Create an empty list `result`.
3. For each character `ch` in `order`:
   1. Append `ch` exactly `count[ch]` times.
   2. Remove it from the count map.
4. Append all remaining characters from the count map.
5. Join the list into a string.

## Correctness

The algorithm first counts every character in `s`, so it knows exactly how many copies of each character must appear in the output.

Then it processes characters in the same order as `order`. For every character `ch` in `order`, the algorithm appends all copies of `ch` before moving to the next character. Therefore, if character `x` appears before character `y` in `order`, all copies of `x` are appended before all copies of `y`.

After that, the algorithm appends characters not present in `order`. The problem allows these characters to appear anywhere, so placing them at the end is valid.

Every character from `s` is appended exactly as many times as it appears in `s`, and no extra characters are added. Therefore, the result is a valid permutation of `s` that respects the custom order.

## Complexity

Let `n = len(s)` and `m = len(order)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | Count `s`, process `order`, then append leftovers |
| Space | `O(n)` | The output list stores the result |

The count map stores at most `26` lowercase letters, so auxiliary counting space is `O(1)` with respect to input size.

## Implementation

```python
from collections import Counter

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        count = Counter(s)
        result = []

        for ch in order:
            if ch in count:
                result.append(ch * count[ch])
                del count[ch]

        for ch, freq in count.items():
            result.append(ch * freq)

        return "".join(result)
```

## Code Explanation

We count every character in `s`:

```python
count = Counter(s)
```

The result is built as a list of string pieces:

```python
result = []
```

Then we process `order` from left to right:

```python
for ch in order:
```

If `ch` appears in `s`, append all its copies:

```python
result.append(ch * count[ch])
```

Then remove it from the counter so it will not be appended again later:

```python
del count[ch]
```

Finally, append characters not mentioned in `order`:

```python
for ch, freq in count.items():
    result.append(ch * freq)
```

The problem allows these remaining characters to go anywhere, so appending them at the end is valid.

Return the joined string:

```python
return "".join(result)
```

## Alternative: Custom Sorting

A shorter solution uses a rank map and Python sorting.

```python
class Solution:
    def customSortString(self, order: str, s: str) -> str:
        rank = {ch: i for i, ch in enumerate(order)}
        return "".join(sorted(s, key=lambda ch: rank.get(ch, len(order))))
```

This is concise, but it costs `O(n log n)` time because it sorts the characters.

## Testing

```python
def is_valid(order: str, s: str, result: str) -> bool:
    if sorted(s) != sorted(result):
        return False

    position = {ch: i for i, ch in enumerate(order)}

    filtered = [ch for ch in result if ch in position]

    for i in range(1, len(filtered)):
        if position[filtered[i - 1]] > position[filtered[i]]:
            return False

    return True

def run_tests():
    sol = Solution()

    result = sol.customSortString("cba", "abcd")
    assert is_valid("cba", "abcd", result)

    result = sol.customSortString("bcafg", "abcd")
    assert is_valid("bcafg", "abcd", result)

    result = sol.customSortString("kqep", "pekeq")
    assert is_valid("kqep", "pekeq", result)

    result = sol.customSortString("abc", "xyz")
    assert is_valid("abc", "xyz", result)

    result = sol.customSortString("abc", "aaabbbccc")
    assert is_valid("abc", "aaabbbccc", result)

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| `"cba", "abcd"` | Standard custom order case |
| `"bcafg", "abcd"` | Extra characters not in `order` |
| `"kqep", "pekeq"` | Duplicate characters in `s` |
| `"abc", "xyz"` | No characters from `s` appear in `order` |
| `"abc", "aaabbbccc"` | Many repeated ordered characters |