Xhin
insertion, deletion, or substitution

You might want to define what those terms actually mean for other audiences.

Example 1: Benyam and Ephrem have a Levenshtein Distance of 5. Simply 5 substitutions.

Alternately, you can do three substitutions, an insert and a delete.

Given two strings, determine the Levenshtein Distance between them

Take whatever they have in common in sequential order and remove those from the strings. The maximum length of what's left on either one is your levensheim distance. So for example:

Benyam -- Ephrem

1. Bnya (4) -- Phrem (5) (the e and m are matches, or at least they were in my solution).

2. Maximum length is 5, so levensheim distance is 5.

Intuitively it seems like this kind of solution would catch more cases than just looking at letters in the same position, however there would probably be some implementation difficulties in building an algorithm for it because you'd need the deletes/inserts to line up the letter order to be worth equal to or less the bonus from having that extra letter in there. In this case it's worth it but the levensheim distance ends up being the same as ghowilo's e-ignoring solution.

Kitten -- Sitting

1. Ke (2) -- Sig (3) (removed -itt-n)

2. Your max length is 3, so 3 is your levensheim distance.

Much more straightforward in this case.

Building an algorithm looks like it would be a fun side challenge so I'll do that soon as well.

Posted October 8th, 2019
by Xhin