Shortest Completing Word Python Solution

lcpy gen -n 748   # by problem number
lcpy gen -s shortest_completing_word   # by problem name

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.

Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.

from collections import Counter


class Solution:
    # Time: O(n * (m + k)) - n words, m word length, k <= 7 plate letters
    # Space: O(1) - at most 26 letters per counter
    def shortest_completing_word(self, license_plate: str, words: list[str]) -> str:
        need = Counter(c for c in license_plate.lower() if c.isalpha())
        best: str | None = None
        for word in words:
            count = Counter(word)
            if all(count[ch] >= k for ch, k in need.items()) and (
                best is None or len(word) < len(best)
            ):
                best = word
        return best or ""