LC 0791 [M] Custom Sort String - ALawliet/algorithms GitHub Wiki

we want to permute a string, a permutation has same chars and number of chars, so we can use a hashmap

we want an ordering, so we handle the ordered chars first

T: O(order + string)
S: O(string)
class Solution:
    def customSortString(self, order: str, s: str) -> str:        
        counter = Counter(s)
        # print(counter)
        res = []
        
        # match the chars that have order first
        for c in order:
            if c in counter:
                freq = counter[c]
                res += c*freq
                counter.pop(c) # del counter[c] # weird step where you remove it completely on first encounter (oh because we already consumed all the freq)
                
        # then it's in already ordered above so we can just dump the remaining at the end because they aren't in the order
        for c, freq in counter.items():
            res += c*freq
        # print(res)
        
        return ''.join(res)