I might be misunderstanding, but doesn't that treat 'abc' and 'cba' as distance 0? Regardless, I was also thinking Levenshtein is sub-optimal, and that you can

I might be misunderstanding, but doesn't that treat 'abc' and 'cba' as distance 0? Regardless, I was also thinking Levenshtein is sub-optimal, and that you can probably solve it in O(n+m). Even if you go for Levenshtein first, you should identify a simple modification to stop calculating the matrix early if the distance is necessarily greater than 1. Get a bit fancier and you can just 'go down the diagonal' and greatly optimize the algorithm.