2025-07-31 14:05:37 +0000 UTC

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        freq = defaultdict(int)
        for char in licensePlate:
            if char == " " or char.isnumeric():
                continue
            freq[char.lower()] += 1
        cur_freq = {}
        shortest = None
        for word in words:
            cur_freq.clear()
            cur_freq.update(freq)
            for char in word:
                if not cur_freq:
                    break
                if char not in cur_freq:
                    continue
                new_freq = cur_freq[char] - 1
                if new_freq <= 0:
                    cur_freq.pop(char)
                else:
                    cur_freq[char] = new_freq
            if not cur_freq and (shortest is None or len(word) < len(shortest)):
                shortest = word
        return shortest