Word bucketing in Python
I think the way to optimize it is to try an entirely different approach -- given a pattern that matches all the words in a set, and a new word to add to the set, how do you modify the pattern to match the new word as well?  Simple answer: as long as the non-wild characters in the pattern match the new word, leave them; otherwise change the pattern to have a wildcard at that position.  You could implement this either recursively or iteratively.

from typing import List

WILD = "*"

def build_common_pattern(words: List[str]) -&gt; str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    pattern = words[0]
    for word in words:
        assert len(word) == len(pattern)
        for i in range(len(word)):
            assert word[i] != WILD
            if pattern[i] != word[i]:
                pattern = pattern[:i] + WILD + pattern[i+1:]
    return pattern

print(build_common_pattern(["aaa", "aab", "baa"]))


This is also a potential use case for functools.reduce:

def build_common_pattern(words: List[str]) -&gt; str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    def union(a: str, b: str) -&gt; str:
        result = ""
        assert len(a) == len(b)
        for i in range(len(a)):
            result += a[i] if a[i] == b[i] else WILD
        return result

    return reduce(union, words)