> #pip install python-levenshtein
> from Levenshtein import distance
That doesn't seem in the spirit of the challenge.
That doesn't seem in the spirit of the challenge.
edit: just for fun, as a one-liner:
def levenshtein(a,b): return sum(x!=y for x,y in zip(a, b))
In practice, that would actually be slower on this input, because of the cost of initializing the bitset. But that is not dependent on the input, so computational complexity is unaffected.
edit: Removed description. Yes, you're right, you can't even look at the whole input in constant time.