Deletion Distance between 2 strings
I was solving this problem at Pramp and I have trouble figuring out the algorithm for this problem.


On the contrary, you've done a very good job of coming up with a solution. There are ways to improve it though.

As you note, this is just the Longest Common Subsequence problem in a thin disguise.  The "deletion distance" between two strings is just the total length of the strings minus twice the length of the LCS.

That is, the LCS of dogs (4 characters) and frogs (5 characters) is ogs (3 characters), so the deletion distance is (4 + 5) - 2 * 3 = 3.

Therefore, all you need to do to solve the problem is to get the length of the LCS, so let's solve that problem.

Your solution is pretty good but the primary problem is that it takes O(mn) time and memory if the strings are of length m and n.  You can improve this.  

The first thing to notice is that if the strings have a common prefix or suffix then you can automatically eliminate it.  That is, the deletion distance for Who let the big dogs out? and Who let the little frogs out? is the same as the deletion distance for big d and little fr. It is very cheap and easy to determine if two strings have a common prefix and suffix, and you go from having an array with 25*29 elements to an array with 5*9 elements, a huge win.

The next thing to notice is: you build the entire m*n array up front, but while you are filling in the array, m[i][j] only ever looks at m[i-1][j-1] or m[i-1][j] or m[i][j-1]. Since you never look at an array line that is two away, you don't ever need more than two lines! That is, you can:


allocate and compute the first line
allocate and compute the second line given the first line
throw away the first line; we'll never use it again
allocate and compute the third line from the second line
throw away the second line
… and so on


You still do O(mn) operations, and you still allocate in total the same amount of memory, but you only have a small amount of it in memory at the same time.  If the strings are large, that's a considerable savings.