791. Custom Sort String - Explanation

Description

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 = "xabfcg", s = "bdca"

Output: "abcd"

Explanation: "adbc", "dabc", "abdc" are also valid outputs.

Example 2:

Input: order = "bfg", s = "agbfcdb"

Output: "bbfgacd"

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Custom Comparator

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        rank = {c: i for i, c in enumerate(order)}
        return ''.join(sorted(s, key=lambda c: rank.get(c, 26)))

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Frequency Count

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

        res = []
        for c in order:
            idx = ord(c) - ord('a')
            while count[idx]:
                res.append(c)
                count[idx] -= 1

        for idx in range(26):
            c = chr(ord('a') + idx)
            while count[idx]:
                count[idx] -= 1
                res.append(c)

        return ''.join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$