Code golf edit distance 2 The edit distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other.

This task is simply to write code that determines if two strings have edit distance exactly 2 from each other.  The twist is that your code must run in linear time. That is if the sum of the lengths of the two strings is n then your code should run in O(n) time.

Example of strings with edit distance 2.

elephant elepanto
elephant elephapntv
elephant elephapntt
elephant lephapnt
elephant blemphant
elephant lmphant
elephant velepphant


Examples where the edit distance is not 2. The last number in each row is the edit distance.

elephant elephant 0
elephant lephant 1
elephant leowan 4
elephant leowanb 4
elephant mleowanb 4
elephant leowanb 4
elephant leolanb 4
elephant lgeolanb 5
elephant lgeodanb 5
elephant lgeodawb 6
elephant mgeodawb 6
elephant mgeodawb 6
elephant mgeodawm 6
elephant mygeodawm 7
elephant myeodawm 6
elephant myeodapwm 7
elephant myeoapwm 7
elephant myoapwm 8


You can assume the input strings have only lower case ASCII letters (a-z).

Your code should output something Truthy if the edit distance is 2 and Falsey otherwise.

If you are not sure if your code is linear time, try timing it with pairs of strings of increasing length where the first is all 0s and the second string is one shorter with one of the 0s changed to a 1.  These all have edit distance 2. This is not a good test of correctness of course but a quadratic time solution  will timeout for strings of length 100,000 or more where a linear time solution should still be fast.
Retina 0.8.2, 76 58 bytes

^(.*)(.*¶)\1
$2
(.*)(¶.*)\1$
$2
^.?¶.?$

^.?(.*).?¶.?\1.?$


Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:

^(.*)(.*¶)\1
$2


Delete the common prefix.

(.*)(¶.*)\1$
$2


Delete the common suffix.

^.?¶.?$


Ignore an edit distance of less than two.

^.?(.*).?¶.?\1.?$


Check that only the first and last characters have been edited, so that the edit distance cannot be greater than two in this case.

From a code golf point of view this can be done in 51 bytes but then the regex becomes unbearably slow to execute for longer strings:

^(?!(.*).?(.*)¶\1.?\2$)(.*).?(.*).?(.*)¶\3.?\4.?\5$


Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:

^


Match the whole input.

(?!(.*).?(.*)¶\1.?\2$)


Don't match strings with an edit distance less than two.

(.*).?(.*).?(.*)¶\3.?\4.?\5$


Match strings with an edit distance less than three.