OneAway.md

One Away

Prompt

There are three types of edits that can be made to a string:

• Replace: Replacing a single character with another character on the string
• Insert: Inserting a single character into a string, making it 1 length longer
• Removal: Deleting a single character from a string, making it 1 length shorter

Write a function that takes in two strings, and returns true if the two strings are one "edit" or zero "edits" away from each other (false if not).

Ex:

    oneAway("sick", "lick") // true;
    oneAway("slick", "lick") // true;
    oneAway("lck", "lick") // true;
    oneAway("sick", "lock") // false;
    oneAway("sick", "sicken") // false;

---

---

---

Initial Solution

Let's look a little closer to the three edit operations:

 Replace: 
  - Two strings such as "lock" and "lick" have the same exact length. The difference 
    lies between the second character of each string. This means that replace edits
    essentially are only difference in one place (index).
  
 Remove: 
  - Take strings such as "slick" and "lick", which have different lengths. They are
    essentially the same except there is a shift at some point in the string.
  
 Insert: 
  - Taking a look at the same strings "lick" and "slick", this is the same idea as 
    removal except inverse.

The approach here is to first realize that Replace edits are slightly different from Insert and Remove edits, therefore we will deal with them separately.

We will first divide the work into two helper functions, one dealing with Replace edits (Strings are the same length), and Insert/Remove edits (Strings are 1 length apart).

function oneRemoveAway(shorter, longer) {
  let shortIndex = 0;
  let longIndex = 0;
  let firstEdit = false;

  while(shortIndex < shorter.length) {
    if (shorter[shortIndex] !== longer[longIndex]) {
      if (firstEdit) {
        return false;
      }
      else {
        firstEdit = true;
        longIndex++;
      }
    }
    else {
      shortIndex++;
      longIndex++;
    }
  }
  return true;
}


function oneReplaceAway (strA, strB) {
  let firstEdit = false; // setting a flag to denote an edit

  for (let i = 0; i < strA.length; i++) {
    if (strA[i] !== strB[i]) {
      if (firstEdit) {
        return false;
      }
      else {
        firstEdit = true;
      }
    }
  }

  return true;
}


function oneAway(strA, strB) {
  if (strA.length === strB.length) {
    return oneReplaceAway(strA, strB);
  }

  // Make sure to keep track of the shorter string
  else if (strA.length + 1 === strB.length) {
    return oneRemoveAway(strA, strB);
  }

  else if (strA.length - 1 === strB.length) {
    return oneRemoveAway(strB, strA);
  }

  // If none of the above criteria meet, more than one edit is needed
  return false;
}

---

---

---

Secondary Solution

The logic behind both the replace method and the inser/remove methods are similar in that they want to look for one difference in the two strings. The difference in the two lies in how we handle that difference, with the replace simply flagging the difference while the insert/remove only increments the pointer of the longer string. This allows to combine the solution into one method:

function oneAway(strA, strB) {
  // check the lengths
  if (Math.abs(strA.length - strB.length > 1)) {
    return false;
  }

  // track the shorter and longer string
  let shorter = strA.length < strB.length ? strA : strB;
  let longer = strA.length < strB.length ? strB : strA;

  let shortIndex = 0;
  let longIndex = 0;
  let hasEdit = false;

  while (shortIndex < shorter.length && longIndex < longer.length) {
    if (shorter[shortIndex] !== longer[longIndex]) {
      // If this isn't the first difference found
      if (hasEdit) {
        return false;
      }
      hasEdit = true;

      if (shorter.length === longer.length) {
        shortIndex++; // move the shorter pointer for replace edits
      }
    }
    else {
      shortIndex++; // move the shorter pointer on a match
    }
    longIndex++; // always increment the longer pointer
  }
  
  return true; // replace, remove and insert edits all checked clean
}

Both approaches are valid, depending on the preferences of the interviewer. The runtime of the first solution at worst is O(n), where n is the length of the longest string. The runtime of the second solution at worst is also O(n), where n is the length of the longest string o the shorterst string (Whichever string's index becomes greater than the length first). Both solutions offer constant O(1) Space complexity, as data stored will always be the same in both functions regarless of the string size. Therefore both options are equally viable.

The first offers a more readable solution which is good. The second does not use repeated code, but the drawback is that it is slightly harder to follow. Both solutions follow similar approaches and are both valid. It would be nice to discuss the tradeoff's of both approaches with your interviewer.