Problem

You are given two strings order and s. All the words 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.

Examples

Example 1:

1
2
3
4
5

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:

1
2

Input: order = "cbafg", s = "abcd"
Output: "cbad"

Solution

Method 1 - Sorting

To solve this problem, we need to rearrange the characters of the string s to follow the order specified in order. Here is a step-by-step approach to achieve this:

  1. Create a Mapping: Create a priority map from the custom order string, where each character is assigned an index based on its position in the order string.
  2. Count Characters in s: Count the occurrences of each character in s. This helps in easily constructing the resultant string based on the sorted order.
  3. Construct the Result: Iterate through the order string and add characters to the result based on the count from the previous step. Finally, add any characters from s that were not present in order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public String customSortString(String order, String s) {
        Map<Character, Integer> priorityMap = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            priorityMap.put(order.charAt(i), i);
        }
        
        int[] count = new int[26];
        for (char ch : s.toCharArray()) {
            count[ch - 'a']++;
        }
        
        StringBuilder ans = new StringBuilder();
        for (char ch : order.toCharArray()) {
            while (count[ch - 'a'] > 0) {
                ans.append(ch);
                count[ch - 'a']--;
            }
        }
        
        for (char ch = 'a'; ch <= 'z'; ch++) {
            while (count[ch - 'a'] > 0) {
                ans.append(ch);
                count[ch - 'a']--;
            }
        }
        
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def custom_sort_string(self, order: str, s: str) -> str:
        priority_map = {c: i for i, c in enumerate(order)}
        
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        
        ans = []
        for ch in order:
            while count[ord(ch) - ord('a')] > 0:
                ans.append(ch)
                count[ord(ch) - ord('a')] -= 1
        
        for ch in map(chr, range(97, 123)):  # iterate 'a' to 'z'
            while count[ord(ch) - ord('a')] > 0:
                ans.append(ch)
                count[ord(ch) - ord('a')] -= 1
        
        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n + m) where n is the length of s and m is the length of order. This includes creating the priority map, counting occurrences, and constructing the result.
  • 🧺 Space complexity: O(n + m) for storing the counts of characters and the resultant string.