Cracking the Coding Interview: "Problem 1.5. One Away" I am going one-by-one through problems in the "Cracking the Coding Interview". This question is about problem 1.5. One Away. Since I was never good in "algorithming", any suggestions are highly appreciated.

The very best thing you can do for me is suggest a better approach instead of the "straightforward" fragile code I wrote.

Oh, and since it's pretty much an interview question, performance is important too. The solution I got is O(n) -- bound by the length of the longest string so far (which can be easily fixed by early exit when mismatchCount exceeds 1).

Code

/**
 * Problem:
 *   There are three types of edits that can performed on strings:
 *   insert a character, remove a charachter, or replace a character.
 *   Given two strings, write a function to check if they are one edit (or zero edits) away.
 *
 * Example:
 *   pale, ple   -&gt; true
 *   pales, pale -&gt; true
 *   pale, bale  -&gt; true
 *   pale, bake  -&gt; false
 *
 * Solution:
 *   complexity: O(n)
 */

export function areOneAway(leftWord: string, rightWord: string): boolean {
  let leftIndex = 0;
  let rightIndex = 0;
  let mismatchCount = 0;

  while (leftIndex &lt; leftWord.length &amp;&amp; rightIndex &lt; rightWord.length) {
    const leftChar = leftWord[leftIndex];
    const rightChar = rightWord[rightIndex];

    if (leftChar === rightChar) {
      leftIndex++;
      rightIndex++;
    } else {
      const nextLeftChar = leftWord[leftIndex + 1];
      const nextRightChar = rightWord[rightIndex + 1];

      const leftCharEqualsNextRight = leftChar === nextRightChar;
      const rightCharEqualsNextLeft = rightChar === nextLeftChar;
      const nextLeftEqualsNextRight = nextLeftChar === nextRightChar;

      if (nextLeftEqualsNextRight) {
        leftIndex++;
        rightIndex++;
      } else if (
        leftCharEqualsNextRight &amp;&amp; rightCharEqualsNextLeft ||
        !leftCharEqualsNextRight &amp;&amp; !rightCharEqualsNextLeft
      ) {
        return false;
      } else if (leftCharEqualsNextRight) {
        rightIndex++;
      } else if (rightCharEqualsNextLeft) {
        leftIndex++;
      } else {
        throw new Error('Invariant violated');
      }

      mismatchCount++;
    }
  }

  return ((leftWord.length - leftIndex) + (rightWord.length - rightIndex) + mismatchCount) &lt;= 1;
}


Tests

import { expect } from 'chai';

import { areOneAway } from '../../src/cracking-the-coding-interview/1-5-one-away';

describe(`1-5: OneAway`, () =&gt; {
  [
    { string1: 'pale', string2: 'ple', expectedResult: true },
    { string1: 'pales', string2: 'pale', expectedResult: true },
    { string1: 'pale', string2: 'bale', expectedResult: true },
    { string1: 'pale', string2: 'bake', expectedResult: false },

    { string1: '', string2: '', expectedResult: true },
    { string1: '', string2: ' ', expectedResult: true },
    { string1: ' ', string2: '', expectedResult: true },
    { string1: '', string2: '  ', expectedResult: false },
    { string1: '  ', string2: '', expectedResult: false },
    { string1: '', string2: 'x  ', expectedResult: false },
    { string1: 'x  ', string2: '', expectedResult: false },
    { string1: 'a', string2: 'a', expectedResult: true },

    { string1: 'ab', string2: 'a', expectedResult: true },
    { string1: 'abc', string2: 'a', expectedResult: false },
    { string1: 'abc', string2: 'abc', expectedResult: true },
    { string1: 'a', string2: 'ab', expectedResult: true },
    { string1: 'a', string2: 'abc', expectedResult: false },

    { string1: 'xab', string2: 'xa', expectedResult: true },
    { string1: 'xabc', string2: 'xa', expectedResult: false },
    { string1: 'xabc', string2: 'xabc', expectedResult: true },
    { string1: 'xa', string2: 'xab', expectedResult: true },
    { string1: 'xa', string2: 'xabc', expectedResult: false },
  ].forEach(testCase =&gt; {
    const { string1, string2, expectedResult } = testCase;

    it(`Should return ${expectedResult} for '${string1}' and '${string2}'`, () =&gt; {
      expect(areOneAway(string1, string2)).to.equal(expectedResult);
    });
  });
});
Your code is almost exactly what I would write. The one slight improvement I can recommend is noticing that adding a character to the left string is the exact same thing as removing a character from the right string.



const areOneAway = (left, right) =&gt; {
  if (Math.abs(left.length - right.length) &gt; 1) return false;
  let difference = 0;
  let indexLeft = 0;
  let indexRight = 0;
  while (difference &lt; 2 &amp;&amp; indexLeft &lt; left.length &amp;&amp; indexRight &lt; right.length) {
    if (left[indexLeft] !== right[indexRight]) {
      difference++;
      // Character inserted in left string, or character removed in right string
      if (left[indexLeft + 1] === right[indexRight]) indexLeft++;
      // Character inserted in right string, or character removed in left string
      else if (left[indexLeft] === right[indexRight + 1]) indexRight++;
    }
    indexLeft++;
    indexRight++;
  }
  return difference &lt; 2;
};


let passed = 0;
let failed = 0;

[
  { string1: 'pale', string2: 'ple', expectedResult: true },
  { string1: 'pales', string2: 'pale', expectedResult: true },
  { string1: 'pale', string2: 'bale', expectedResult: true },
  { string1: 'pale', string2: 'bake', expectedResult: false },

  { string1: '', string2: '', expectedResult: true },
  { string1: '', string2: ' ', expectedResult: true },
  { string1: ' ', string2: '', expectedResult: true },
  { string1: '', string2: '  ', expectedResult: false },
  { string1: '  ', string2: '', expectedResult: false },
  { string1: '', string2: 'x  ', expectedResult: false },
  { string1: 'x  ', string2: '', expectedResult: false },
  { string1: 'a', string2: 'a', expectedResult: true },

  { string1: 'ab', string2: 'a', expectedResult: true },
  { string1: 'abc', string2: 'a', expectedResult: false },
  { string1: 'abc', string2: 'abc', expectedResult: true },
  { string1: 'a', string2: 'ab', expectedResult: true },
  { string1: 'a', string2: 'abc', expectedResult: false },

  { string1: 'xab', string2: 'xa', expectedResult: true },
  { string1: 'xabc', string2: 'xa', expectedResult: false },
  { string1: 'xabc', string2: 'xabc', expectedResult: true },
  { string1: 'xa', string2: 'xab', expectedResult: true },
  { string1: 'xa', string2: 'xabc', expectedResult: false },
].forEach(testCase =&gt; {
  const { string1, string2, expectedResult } = testCase;

  if (expectedResult !== areOneAway(string1, string2)) {
    console.log(`Failed: areOneAway('${string1}', '${string2}') should be ${expectedResult}`);
    failed++;
  } else {
    passed++;
  }
});
console.log('Passed:', passed, 'Failed:', failed)




Of course, the next step for making this function more reusable would be to extract the difference calculation to a separate function.



const findDifference = (left, right) =&gt; {
  let difference = 0;
  let indexLeft = 0;
  let indexRight = 0;
  while (indexLeft &lt; left.length &amp;&amp; indexRight &lt; right.length) {
    if (left[indexLeft] !== right[indexRight]) {
      difference++;
      if (left[indexLeft + 1] === right[indexRight]) indexLeft++;
      else if (left[indexLeft] === right[indexRight + 1]) indexRight++;
    }
    indexLeft++;
    indexRight++;
  }
  difference += left.length - indexLeft;
  difference += right.length - indexRight;
  return difference
}

let passed = 0;
let failed = 0;
[
  { string1: 'pale', string2: 'ple', expectedResult: 1 },
  { string1: 'pales', string2: 'pale', expectedResult: 1 },
  { string1: 'pale', string2: 'bale', expectedResult: 1 },
  { string1: 'pale', string2: 'bake', expectedResult: 2 },

  { string1: '', string2: '', expectedResult: 0 },
  { string1: '', string2: ' ', expectedResult: 1 },
  { string1: ' ', string2: '', expectedResult: 1 },
  { string1: '', string2: '  ', expectedResult: 2 },
  { string1: '  ', string2: '', expectedResult: 2 },
  { string1: '', string2: 'x  ', expectedResult: 3 },
  { string1: 'x  ', string2: '', expectedResult: 3 },
  { string1: 'a', string2: 'a', expectedResult: 0 },

  { string1: 'ab', string2: 'a', expectedResult: 1 },
  { string1: 'abc', string2: 'a', expectedResult: 2 },
  { string1: 'abc', string2: 'abc', expectedResult: 0 },
  { string1: 'a', string2: 'ab', expectedResult: 1 },
  { string1: 'a', string2: 'abc', expectedResult: 2 },

  { string1: 'xab', string2: 'xa', expectedResult: 1 },
  { string1: 'xabc', string2: 'xa', expectedResult: 2 },
  { string1: 'xabc', string2: 'xabc', expectedResult: 0 },
  { string1: 'xa', string2: 'xab', expectedResult: 1 },
  { string1: 'xa', string2: 'xabc', expectedResult: 2 },
].forEach(test =&gt; {
  const { string1, string2, expectedResult } = test
  const result = findDifference(string1, string2)
  if (result !== expectedResult) {
    console.log(`Failed: findDifference('${string1}', '${string2}') should be ${expectedResult}, got ${result}`);
    failed++;
  } else {
    passed++;
  }
});
console.log('Passed:', passed, 'Failed:', failed)




With this helper, areNAway could be implemented very easily and areOneAway could just be implemented as (left, right) =&gt; areNAway(left, right, 1)

const areNAway = (left, right, n) =&gt; {
  if (Math.abs(left.length - right.length) &gt; n) return false;
  return findDifference(left, right) &lt;= n;
}


P.S. You may be interested in the "Official" solution. It is available on GitHub.