Dolne ograniczenie wynika z tego, że pojedyncze wstawienie lub usunięcie zmienia długość ciągu tylko o 1. Górne ograniczenie można osiągnąć przez zamianę symboli w części o wspólnej długości, a następnie wstawienie lub usunięcie pozostałych symboli.
Jeżeli oba ciągi mają tę samą długość, odległość Hamminga jest górnym ograniczeniem odległości Levenshteina:
Odległość Hamminga dopuszcza wyłącznie zamiany i jest bezpośrednio definiowana dla ciągów tej samej długości.
Jeżeli nie dopuszcza się zamian, a jedynie wstawienia i usunięcia, to minimalna liczba operacji dla ciągów długości i wynosi
gdzie jest długością najdłuższego wspólnego podciągu. Zależność ta nie przechodzi wprost na klasyczną odległość Levenshteina, ponieważ zamiana kosztuje w niej 1, a nie 2 jak usunięcie połączone z wstawieniem.
Obliczanie Programowanie dynamiczne
Standardowy algorytm wykorzystuje programowanie dynamiczne.