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 - Counting (Order-based Bucket Sort)

To solve this problem we use a counting/bucket approach: count each character in s, then emit characters in the order specified by order, followed by any leftover characters. This is effectively an order-based bucket sort and is optimal for small fixed alphabets.

  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

#include <string>
#include <vector>
using namespace std;

class Solution {
 public:
  string customSortString(string order, string s) {
    vector<int> count(26, 0);
    for (char c : s) count[c - 'a']++;
    string ans;
    for (char c : order) {
      if (count[c - 'a'] > 0) {
        ans += string(count[c - 'a'], c);
        count[c - 'a'] = 0;
      }
    }
    for (char c = 'a'; c <= 'z'; ++c) {
      if (count[c - 'a'] > 0) ans += string(count[c - 'a'], c);
    }
    return ans;
  }
};
 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

package main

import (
  "strings"
)

func customSortString(order string, s string) string {
  count := make([]int, 26)
  for _, ch := range s {
    count[ch-'a']++
  }
  var sb strings.Builder
  for _, ch := range order {
    if count[ch-'a'] > 0 {
      sb.WriteString(strings.Repeat(string(ch), count[ch-'a']))
      count[ch-'a'] = 0
    }
  }
  for ch := 'a'; ch <= 'z'; ch++ {
    if count[ch-'a'] > 0 {
      sb.WriteString(strings.Repeat(string(ch), count[ch-'a']))
    }
  }
  return sb.String()
}
 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

class Solution {
  fun customSortString(order: String, s: String): String {
    val count = IntArray(26)
    for (ch in s) count[ch - 'a']++
    val sb = StringBuilder()
    for (ch in order) {
      repeat(count[ch - 'a']) { sb.append(ch) }
      count[ch - 'a'] = 0
    }
    for (ch in 'a'..'z') repeat(count[ch - 'a']) { sb.append(ch) }
    return sb.toString()
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from typing import List

class Solution:
  def customSortString(self, order: str, s: str) -> str:
    count = [0] * 26
    for ch in s:
      count[ord(ch) - ord('a')] += 1

    ans: List[str] = []
    for ch in order:
      while count[ord(ch) - ord('a')] > 0:
        ans.append(ch)
        count[ord(ch) - ord('a')] -= 1

    for i in range(26):
      ch = chr(ord('a') + i)
      while count[i] > 0:
        ans.append(ch)
        count[i] -= 1

    return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

pub struct Solution;
impl Solution {
  pub fn custom_sort_string(order: String, s: String) -> String {
    let mut count = vec![0usize; 26];
    for b in s.bytes() { count[(b - b'a') as usize] += 1; }
    let mut ans = String::new();
    for b in order.bytes() {
      let idx = (b - b'a') as usize;
      for _ in 0..count[idx] { ans.push(b as char); }
      count[idx] = 0;
    }
    for i in 0..26 {
      for _ in 0..count[i] { ans.push((b'a' + i as u8) as char); }
    }
    ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function customSortString(order: string, s: string): string {
  const count: number[] = new Array(26).fill(0);
  for (const ch of s) count[ch.charCodeAt(0) - 97]++;
  let ans = '';
  for (const ch of order) {
    ans += ch.repeat(count[ch.charCodeAt(0) - 97]);
    count[ch.charCodeAt(0) - 97] = 0;
  }
  for (let i = 0; i < 26; i++) {
    if (count[i] > 0) ans += String.fromCharCode(97 + i).repeat(count[i]);
  }
  return 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.