One Edit

Tags

One Edit

Category

Strings

Difficulty

Medium

Problem Statement

Given two strings, determine if they are one edit (or zero edits) apart. An edit is defined as: inserting a character, deleting a character, or replacing a character. Return true if the strings are at most one edit apart, false otherwise.

Intuition

If the strings are the same length, the only possible edit is a replacement, so at most one position can differ. If the lengths differ by one, the only possible edit is an insertion or deletion, so we can walk through both strings and allow at most one skip. If the lengths differ by more than one, no single edit can transform one into the other.

Approach

  1. If the absolute difference in lengths is greater than 1, return false immediately.
  2. If the strings have equal length, check for a replacement:
    • Walk through both strings simultaneously.
    • Count the number of positions where characters differ.
    • Return true if the count is at most 1.
  3. If the lengths differ by exactly 1, check for an insertion/deletion:
    • Use two pointers, one for each string.
    • Walk through both strings. When a mismatch is found, advance the pointer in the longer string (simulating a deletion from the longer or insertion into the shorter).
    • Allow at most one such mismatch.
  4. Return whether at most one edit was found.

Pseudocode

function oneEdit(stringOne, stringTwo):
    lenOne = len(stringOne)
    lenTwo = len(stringTwo)

    if abs(lenOne - lenTwo) > 1:
        return false

    madeEdit = false
    i = 0
    j = 0
    while i < lenOne and j < lenTwo:
        if stringOne[i] != stringTwo[j]:
            if madeEdit:
                return false
            madeEdit = true
            if lenOne == lenTwo:
                i += 1
                j += 1
            elif lenOne > lenTwo:
                i += 1
            else:
                j += 1
        else:
            i += 1
            j += 1

    return true

Time & Space Complexity

  • Time: O(n) where n is the length of the shorter string. We make a single pass through both strings.
  • Space: O(1) - only a few pointer variables and a boolean flag.

Key Insights

  • The length difference immediately determines which type of edit is possible (replace vs insert/delete).
  • A length difference greater than 1 makes it impossible with a single edit.
  • The two-pointer technique elegantly handles insertion and deletion as the same operation viewed from different perspectives.

Edge Cases

  • Two identical strings: zero edits needed, return true.
  • Empty string and single-character string: one insertion, return true.
  • Both strings empty: return true.
  • Empty string and a two-character string: two edits needed, return false.
  • Strings differing only at the last character: one replacement, return true.
  • Strings where the first character differs: the edit is detected early but the rest must still match.

Linked mentions