791.CustomSortString.py

'''
    order and str are strings composed of lowercase letters. 
    In order, no letter occurs more than once.

    order was sorted in some custom order previously. We want
    to permute the characters of str so that they match the 
    order that order was sorted. More specifically, if x 
    occurs before y in order, then x should occur before y 
    in the returned string.

    Return any permutation of str (as a string) that satisfies 
    this property.

    Example:
    Input: 
    order = "cba"
    str = "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.

    Note:
        - order has length at most 26, and no character is 
          repeated in order.
        - str has length at most 200.
        - order and str consist of lowercase letters only.
'''
#Difficulty: Medium
#39 / 39 test cases passed.
#Runtime: 16 ms
#Memory Usage: 14.3 MB

#Runtime: 16 ms, faster than 100.00% of Python3 online submissions for Custom Sort String.
#Memory Usage: 14.3 MB, less than 52.49% of Python3 online submissions for Custom Sort String.

from collections import Counter

class Solution:
    def customSortString(self, S: str, T: str) -> str:
        string = ''
        letters = Counter(T)
        for char in S:
            string += char * letters[char]
            del letters[char]
        for char in letters:
            string += char * letters[char]
        return string