# yigid balaban <fyb@fybx.dev>
# neetcode                      2024
# easy / shortest completing word

def solution(licensePlate: str, words: list[str]) -> str:
    licensePlate = ''.join([c.lower() for c in licensePlate if not c.isdigit()]).replace(' ', '')
    words = sorted(words, key=len)
    scores = []

    pw = 0
    lp = licensePlate
    score = 0
    while True:
        for c in words[pw]:
            if c in lp:
                score += 1
                lp = lp.replace(c, '', 1)
        if len(lp) == 0:
            return words[pw]
        scores.append(score)
        score = 0
        lp = licensePlate
        pw += 1

        if pw >= len(words):
            break

    smallest_first = 0
    for ps in range(len(scores) - 1, -1, -1):
        if scores[ps] >= scores[smallest_first]:
            smallest_first = ps
    return words[smallest_first]


print(solution("1s3 PSt", ["step","steps","stripe","stepple"]) == "steps")
print(solution("1s3 456", ["looks","pest","stew","show"]) == "pest")
print(solution("GrT 390b7", ["trobbg", "robotgrt", "gtrb"]) == "gtrb")
print(solution("q4L Mx37 o", ["loxm", "qlmox", "mloxq"]) == "qlmox")
print(solution("A1B2C3", ["abccdef", "bcabc", "aabbcc", "cbca"]) == "cbca")
print(solution("M6k39 Jdf 21", ["mfkjd", "mkfjddd", "mjjkfd", "jfdmk"]) == "mfkjd")
print(solution("Th9X9er5", ["thexer", "therxx", "xether", "thxere"]) == "thexer")