791. Custom Sort String

Problem Statement

link: LeetCode.cn LeetCode 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:

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

Input: order = "bcafg", s = "abcd" Output: "bcad"

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

Solution Approach

Algorithm

Complexity

time complexity: O(n) space complexity: O(n)

Implement

    class Solution:
        def customSortString(self, order: str, s: str) -> str:
            freq = Counter(s)
            ans = list()
            for ch in order:
                if ch in freq:
                    ans.extend([ch] * freq[ch])
                    freq[ch] = 0
            for (ch, k) in freq.items():
                if k > 0:
                    ans.extend([ch] * k)
            return "".join(ans)

    

    
    

Twitter  facebook  Email