PRAMP — Deletion Distance

This is a pretty popular question technical interview. It’s not only in Cracking the Coding Interview, but in numerous other technical interview resources: Leetcode, Code Wars, etc.

Here is the question:

“ The deletion distance of two strings is the minimum number of characters you need to delete in the two strings in order to get the same string. For instance, the deletion distance between "heat" and "hit" is 3:

By deleting 'e' and 'a' in "heat", and 'i' in "hit", we get the string "ht" in both cases.

We cannot get the same string from both strings by deleting 2 letters or fewer.

Given the strings str1 and str2, write an efficient function deletionDistance that returns the deletion distance between them. Explain how your function works, and analyze its time and space complexities.”

Here are some examples:

input: str1 = “dog”, str2 = “frog” , output: 3

input: str1 = “some”, str2 = “some” , output: 0

input: str1 = “some”, str2 = “thing” , output: 9

input: str1 = “”, str2 = “”, output: 0

To solve this problem,

1. Create a hash (for our frequency counter)
2. Initialize a variable = 0 (this will act as the counter)
3. Concat both strings into one string
4. Loop over the concatenated string and create the key value pairs for the frequency counter hash.
5. Map over the hash using Object.keys(hash).map. If the value is equal to 1, increase the count variable
6. Return the count variable.

Edge Case: if the string is less than or equal to two characters, and the first and second string are both two characters long, AND if the first and second letters in both strings are different, return 2.

Here is the code:

This passes the tests in Pramp. There are other ways to do it, but this way worked for me!

Happy Hacking.

-Crystal