# Custom Sort String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/custom-sort-string)
Canonical: https://scaleengineer.com/dsa/problems/custom-sort-string
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
**Companies:** [Snap](https://scaleengineer.com/companies/snap)
---
## Problem
You are given two strings `order` and `s`. All the characters of `order` are **unique** and were sorted in some custom order previously.

Permute the characters of `s` so that they match the order that `order` was sorted. More specifically, if a character `x` occurs before a character `y` in `order`, then `x` should occur before `y` in the permuted string.

Return _any permutation of_ `s` _that satisfies this property_.

**Example 1:**

**Input:**  order = "cba", s = "abcd" 

**Output:**  "cbad" 

**Explanation:** `"a"`, `"b"`, `"c"` appear in order, so the order of `"a"`, `"b"`, `"c"` should be `"c"`, `"b"`, and `"a"`.

Since `"d"` does not appear in `order`, it can be at any position in the returned string. `"dcba"`, `"cdba"`, `"cbda"` are also valid outputs.

**Example 2:**

**Input:**  order = "bcafg", s = "abcd" 

**Output:**  "bcad" 

**Explanation:**  The characters `"b"`, `"c"`, and `"a"` from `order` dictate the order for the characters in `s`. The character `"d"` in `s` does not appear in `order`, so its position is flexible.

Following the order of appearance in `order`, `"b"`, `"c"`, and `"a"` from `s` should be arranged as `"b"`, `"c"`, `"a"`. `"d"` can be placed at any position since it's not in order. The output `"bcad"` correctly follows this rule. Other arrangements like `"dbca"` or `"bcda"` would also be valid, as long as `"b"`, `"c"`, `"a"` maintain their order.

**Constraints:**

* `1 <= order.length <= 26`
* `1 <= s.length <= 200`
* `order` and `s` consist of lowercase English letters.
* All the characters of `order` are **unique**.

# Approaches
## Custom Sorting with a Comparator
This approach involves defining a custom order for characters based on the `order` string and then using a standard sorting algorithm to sort the characters of string `s`. The custom order is established by mapping each character in `order` to its index. Characters not in `order` are given a default, higher rank to ensure they appear at the end.
**Time:** O(L + N log N), where L is the length of `order` and N is the length of `s`. Building the rank map takes O(L). Sorting `s` takes O(N log N). Building the final string takes O(N). · **Space:** O(N + L), where L is the length of `order` and N is the length of `s`. We need O(L) space for the rank map (or O(1) for a fixed alphabet) and O(N) space for the character array used for sorting. Given L <= 26, this simplifies to O(N).
**Pros:** Conceptually straightforward, as it leverages familiar built-in sorting functions.; Relatively easy to implement.
**Cons:** The time complexity of O(N log N) is not optimal for this problem.; It involves converting the primitive `char`s of the string to `Character` objects, which introduces some memory and performance overhead.
### Explanation
The core idea is to translate the custom sorting problem into a standard sorting problem by providing a custom comparison logic.

First, we create a 'rank' map (an array is efficient for characters) to store the position of each character as defined by the `order` string. We iterate through `order`, and for each character `c` at index `i`, we set its rank to `i`. Any character not present in `order` will have a default rank, typically a value larger than any rank from `order`, so they are sorted to the end.

Next, we convert the string `s` into an array of characters, which can be sorted.

We then apply a sorting algorithm (like `Arrays.sort`) to this array, passing our custom comparator. The comparator uses the pre-computed ranks to decide the order of any two characters.

Finally, the sorted array of characters is converted back into a string.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String customSortString(String order, String s) {
        // Create an array to store the rank of each character.
        int[] rank = new int[26];
        // A large value for characters not in 'order'.
        Arrays.fill(rank, 27); 
        for (int i = 0; i < order.length(); i++) {
            rank[order.charAt(i) - 'a'] = i;
        }

        // Convert string 's' to a Character array to sort it.
        Character[] sChars = new Character[s.length()];
        for (int i = 0; i < s.length(); i++) {
            sChars[i] = s.charAt(i);
        }

        // Sort the character array using a custom comparator based on rank.
        Arrays.sort(sChars, (c1, c2) -> rank[c1 - 'a'] - rank[c2 - 'a']);

        // Build the result string from the sorted character array.
        StringBuilder result = new StringBuilder(sChars.length);
        for (Character c : sChars) {
            result.append(c);
        }
        return result.toString();
    }
}
```
### Algorithm
- Create an integer array `rank` of size 26, initialized with a large value (e.g., 27).
- Iterate through the `order` string. For each character `c` at index `i`, set `rank[c - 'a'] = i`.
- Convert the input string `s` into a `Character` array `sChars`.
- Sort `sChars` using `Arrays.sort` and a custom `Comparator`.
- The comparator logic is `(c1, c2) -> rank[c1 - 'a'] - rank[c2 - 'a']`.
- Construct a new string by joining the characters in the sorted array and return it.

## Counting Sort with Frequency Map
This approach uses a frequency map (or a simple array) to count the occurrences of each character in string `s`. It then constructs the result string by first appending characters in the order specified by the `order` string, followed by any remaining characters. This avoids a direct comparison-based sort, leading to a more efficient linear time complexity.
**Time:** O(N + L), where N is the length of `s` and L is the length of `order`. It takes O(N) to count frequencies, O(L + N) to build the string based on `order` (total appends are at most N), and O(1 + N) to append the remaining characters. · **Space:** O(N). We use an O(1) array (size 26) for frequency counts and a `StringBuilder` which requires O(N) space to construct the result string.
**Pros:** Highly efficient with a linear time complexity of O(N + L), which is optimal.; Simple to implement and understand, using basic array and string manipulations.
**Cons:** This specific implementation appends remaining characters in alphabetical order. While valid, if a different order for remaining characters is desired, the final loop would need modification.
### Explanation
This method is based on the idea of counting sort, which is highly efficient for data with a small range of keys, like lowercase English letters.

First, we iterate through the string `s` and count the frequency of each character. An integer array of size 26 is perfect for this, where `counts[0]` stores the frequency of 'a', `counts[1]` for 'b', and so on.

Next, we initialize a `StringBuilder` to build our result. We iterate through the `order` string. For each character `c` in `order`, we look up its count in our frequency array. We append `c` to our `StringBuilder` that many times and then reset its count to zero. This ensures that these characters are placed first and in the correct custom order.

Finally, there might be characters in `s` that were not in `order`. Their counts in the frequency array are still non-zero. We iterate through our frequency array from 'a' to 'z'. For any character with a remaining count, we append it to the `StringBuilder`. These characters will appear at the end of the result string, and their relative order will be alphabetical (though any order is acceptable for them).

The final result is obtained by converting the `StringBuilder` to a string.

```java
class Solution {
    public String customSortString(String order, String s) {
        // Step 1: Count frequencies of characters in s.
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        StringBuilder result = new StringBuilder();

        // Step 2: Append characters based on the 'order' string.
        for (char c : order.toCharArray()) {
            while (counts[c - 'a'] > 0) {
                result.append(c);
                counts[c - 'a']--;
            }
        }

        // Step 3: Append remaining characters.
        for (int i = 0; i < 26; i++) {
            while (counts[i] > 0) {
                result.append((char) ('a' + i));
                counts[i]--;
            }
        }

        return result.toString();
    }
}
```
### Algorithm
- Create an integer array `counts` of size 26 to store the frequency of each character in `s`.
- Iterate through `s` and populate the `counts` array.
- Initialize an empty `StringBuilder` to build the result.
- Iterate through the `order` string. For each character `c`, append it to the `StringBuilder` `counts[c - 'a']` times, then set its count to 0.
- Iterate through the `counts` array from index 0 to 25. For each index `i` with a non-zero count, append the corresponding character `(char)('a' + i)` to the `StringBuilder` that many times.
- Return the string from the `StringBuilder`.

# Solutions
### Java

```java
class Solution {
public
  String customSortString(String order, String s) {
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < order.length(); ++i) {
      char c = order.charAt(i);
      while (cnt[c - 'a']-- > 0) {
        ans.append(c);
      }
    }
    for (int i = 0; i < 26; ++i) {
      while (cnt[i]-- > 0) {
        ans.append((char)('a' + i));
      }
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string customSortString(string order, string s) {
    int cnt[26] = {0};
    for (char &c : s)
      ++cnt[c - 'a'];
    string ans;
    for (char &c : order)
      while (cnt[c - 'a']-- > 0)
        ans += c;
    for (int i = 0; i < 26; ++i)
      if (cnt[i] > 0)
        ans += string(cnt[i], i + 'a');
    return ans;
  }
};

```

### Python

```python
class Solution:
    def customSortString(self, order: str, s: str) -> str: cnt = Counter(s) ans = [] for c in order: ans . append(c * cnt[c]) cnt[c] = 0 for c, v in cnt . items(): ans . append(c * v) return '' . join(ans)

```