> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/701-800/custom-sort-string.md).

# 791. Custom Sort String

### Description

`order` and `str` are strings composed of lowercase letters. In `order`, no letter occurs more than once.

`order` was sorted in some custom order previously. We want to permute the characters of `str` so that they match the order that `order` was sorted. More specifically, if `x` occurs before `y` in `order`, then `x` should occur before `y` in the returned string.

Return any permutation of `str` (as a string) that satisfies this property.

### Constraints

* `order` has length at most `26`, and no character is repeated in `order`.
* `str` has length at most `200`.
* `order` and `str` consist of lowercase letters only.

### Approach

### Links

* Binarysearch
* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/custom-sort-string/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:**

order = "cba"

str = "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.
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(MAX(m, n)), where m & n is the length of order & str String
 * Space complexity : O(n)
 */

class Solution {
    public String customSortString(String order, String str) {
        int[] count = new int[26];
        for(char ch: str.toCharArray()) {
            count[ch-'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for(char ch: order.toCharArray()) {
            while(count[ch-'a']-- > 0) {
                sb.append(ch);
            }
        }
        
        for(char ch = 'a'; ch <= 'z'; ch++) {
            while(count[ch-'a']-- > 0) {
                sb.append(ch);
            }
        }
        
        return sb.toString();
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*