oneOrLessEdits.ts

// Can make an insert, remove, replace
// find out if two strings are one or zero edits away from each others
function hasOneOrLessEdits(str1: string, str2: string): boolean {
  // Best case is O(N) since the string should be the same size, if they are not then we know they the answer is false
  debugger
  if (Math.abs(str1.length - str2.length) > 1) {
    return false
  }
  
  let countEdits = 0

  // if same length then make sure at most 1 character has changed
  if (str1.length === str2.length) {
    for (let i = 0; i < str1.length; ++i) {
      const char1 = str1[i]
      const char2 = str2[i]

      if (char1 !== char2 && countEdits++ > 1) {
        return false
      }
    }
    return countEdits <= 1
  }

  let i1 = 0
  let i2 = 0

  while (i1 <= str1.length && i2 <= str2.length) {
    const char1 = str1[i1]
    const char2 = str2[i2]

    if (char1 !== char2) {
      const primaryStr = str1.length > str2.length ? str1 : str2
      const secondaryStr = str1.length > str2.length ? str2 : str1

      const remainingPrimaryStrChars = primaryStr.slice(i1 + 1, primaryStr.length)
      const remainingSecondaryStrChars = secondaryStr.slice(i2, secondaryStr.length)
        
      if (remainingPrimaryStrChars.length !== remainingSecondaryStrChars.length) throw 'Substrings should be the same length at this point'

      if (remainingPrimaryStrChars === remainingSecondaryStrChars) {
        return true
      }
      return false
    }

    i1++
    i2++
  }

  return true
}