Edit distance between two strings, in the unit-cost convention also called Levenshtein distance, is the minimum number of single-symbol insertions, deletions, and substitutions needed to transform one into the other (CRC Press LLC 2019). Each operation costs one. For example, the edit distance from cat to cart is 1, achieved by inserting r.
Unlike Hamming distance, edit distance permits changes in length. Even for equal-length strings, insertions and deletions can cost less than replacing every differing symbol. For example, abc and bca have Hamming distance 3 but edit distance 2.
Let 
be the least metric
embedding distortion into the real space 
of absolutely summable sequences
for all strings of length at most 
over a finite alphabet 
, including the empty string.
The norm on 
is 
.
