791. Custom Sort String, 1122. Relative Sort Array

T: O(nlogn)

S: O(n)

```java
class Solution {
    public String customSortString(String order, String s) {
        int[] ord = new int[26];
        Arrays.fill(ord, 26); // max is 26
        for (int i = 0; i < order.length(); i++) {
            ord[order.charAt(i) - 'a'] = i;
        }

        List<Character> cc = new ArrayList<>();
        for (char ch : s.toCharArray()) {
            cc.add(ch);
        }

        Collections.sort(cc, (a, b) -> {
            return ord[a - 'a'] - ord[b - 'a'];
        });
        
        StringBuilder result = new StringBuilder();
        for (char c : cc) {
            result.append(c);
        }
        return result.toString();
    }
}

/**
using fixing order for cba
 */
```

```java
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] rank2 = new int[1001];
        Arrays.fill(rank2, arr2.length);
        for (int i = 0; i < arr2.length; i++) {
            rank2[arr2[i]] = i;
        }
        List<Integer> list1 = new ArrayList<>();
        for (int num : arr1) {
            list1.add(num);
        }
        Collections.sort(list1, (a, b) -> {
            if (rank2[a] == rank2[b]) {
                return a - b;
            }
            return rank2[a] - rank2[b];
        });
        int[] result = new int[arr1.length];
        int i = 0;
        for (int num : list1) {
            result[i++] = num;
        }
        return result;
    }
}
```