LeetCode 161 - One Edit Distance

The problem asks us to determine whether two strings are exactly one edit apart. An edit can be one of three operations: 1. Insert a single character 2. Delete a single character 3. Replace one character with a different character The key detail is the word exactly.

leetcodemediumtwo-pointersstring

LeetCode Problem 161

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

The problem asks us to determine whether two strings are exactly one edit apart. An edit can be one of three operations:

  1. Insert a single character
  2. Delete a single character
  3. Replace one character with a different character

The key detail is the word exactly. The strings must differ by precisely one valid edit. If they are already identical, the answer is false because zero edits are required. If they differ by two or more edits, the answer is also false.

The input consists of two strings, s and t. Their lengths can range from 0 to 10^4, so the solution must handle empty strings and reasonably large inputs efficiently.

The output is a boolean:

  • Return true if one edit transforms one string into the other
  • Return false otherwise

The constraints suggest that an efficient linear scan is appropriate. Since the strings can be large, repeatedly constructing modified strings or exploring all possible edits would be unnecessarily expensive.

Several edge cases are especially important:

  • Both strings are empty, which should return false
  • The strings are already identical, which should also return false
  • The length difference is greater than 1, which immediately makes the answer false
  • One string may be empty while the other contains exactly one character
  • The differing character may appear at the beginning, middle, or end of the strings

A correct solution must distinguish carefully between replacement and insertion/deletion scenarios.

Approaches

Brute Force Approach

A brute force solution would explicitly try every possible edit operation.

For replacements, we could iterate through every position in s and try replacing the character with every possible valid character, then compare the result with t.

For insertions, we could insert every possible character at every possible position.

For deletions, we could remove each character one at a time.

If any generated string equals the target string, we return true.

This approach is correct because it exhaustively checks every valid one-edit transformation. However, it is highly inefficient. Each generated string construction costs linear time, and there are many possible modifications.

Because string lengths can reach 10^4, generating and comparing large numbers of modified strings would be far too slow.

Optimal Two Pointer Approach

The key observation is that we do not need to simulate all edits explicitly.

If two strings are exactly one edit apart, then:

  • Their lengths differ by at most 1
  • They can have at most one mismatch while scanning from left to right

This naturally leads to a two pointer solution.

We compare characters one by one:

  • If the characters match, both pointers move forward

  • If they differ, we consume the single allowed edit

  • If lengths are equal, treat it as a replacement

  • If lengths differ, treat it as insertion/deletion

After using one edit, the remaining parts of the strings must match exactly.

This allows us to solve the problem in linear time with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × alphabet_size × n) O(n) Explicitly generates edited strings
Optimal O(n) O(1) Single linear scan with two pointers

Algorithm Walkthrough

  1. First, compute the lengths of s and t.

If the absolute difference between their lengths is greater than 1, return false immediately. A single edit cannot bridge a gap larger than one character. 2. Ensure that s is the shorter string.

If s is longer than t, swap them. This simplifies the logic because we only need to handle insertion into the shorter string rather than both insertion and deletion separately. 3. Initialize two pointers.

Use:

  • i for traversing s
  • j for traversing t
  1. Traverse both strings together.

While both pointers are within bounds:

  • If s[i] == t[j], move both pointers forward
  • Otherwise, we found the first mismatch
  1. Handle the mismatch carefully.

At the first mismatch:

  • If the strings have equal lengths, this mismatch must represent a replacement, so advance both pointers
  • Otherwise, this mismatch must represent an insertion into the shorter string, so advance only j
  1. After consuming the edit, verify the remainder.

Compare the remaining substrings:

  • s[i:]
  • t[j:]

They must be identical for the strings to be exactly one edit apart. 7. Handle the case where no mismatch was found.

If the loop finishes without mismatches:

  • The strings are one edit apart only if their lengths differ by exactly 1

For example:

  • "abc" and "ab" are valid
  • "abc" and "abc" are not

Why it works

The algorithm relies on the fact that exactly one edit creates at most one structural divergence between the strings. Once the first mismatch is encountered, the remaining portions must align perfectly after accounting for the edit type. By distinguishing equal-length and unequal-length cases, the algorithm correctly models replacement versus insertion/deletion operations.

Python Solution

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        m = len(s)
        n = len(t)

        # Length difference greater than 1 is impossible
        if abs(m - n) > 1:
            return False

        # Make sure s is the shorter string
        if m > n:
            return self.isOneEditDistance(t, s)

        i = 0
        j = 0

        while i < m and j < n:
            if s[i] != t[j]:
                # Replacement case
                if m == n:
                    return s[i + 1:] == t[j + 1:]

                # Insertion/deletion case
                return s[i:] == t[j + 1:]

            i += 1
            j += 1

        # No mismatch found
        return m + 1 == n

The implementation begins by checking whether the length difference exceeds one. If so, it immediately returns False because a single edit cannot compensate for such a gap.

Next, the function ensures that s is always the shorter string. This normalization simplifies the logic because we only need to consider insertion into the shorter string instead of handling insertion and deletion separately.

The two pointers traverse the strings simultaneously. When characters match, both pointers advance normally.

When a mismatch occurs, the algorithm immediately determines which edit type applies:

  • If lengths are equal, the mismatch must be a replacement
  • Otherwise, it must be an insertion into the shorter string

Instead of continuing character-by-character manually, the implementation directly compares the remaining suffixes. If those suffixes match, then exactly one edit explains the difference.

If the loop finishes without any mismatch, the only valid one-edit scenario is when the longer string contains one additional trailing character.

Go Solution

func isOneEditDistance(s string, t string) bool {
    m := len(s)
    n := len(t)

    // Length difference greater than 1 is impossible
    if abs(m-n) > 1 {
        return false
    }

    // Ensure s is the shorter string
    if m > n {
        return isOneEditDistance(t, s)
    }

    i := 0
    j := 0

    for i < m && j < n {
        if s[i] != t[j] {
            // Replacement case
            if m == n {
                return s[i+1:] == t[j+1:]
            }

            // Insertion/deletion case
            return s[i:] == t[j+1:]
        }

        i++
        j++
    }

    // No mismatch found
    return m+1 == n
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in absolute value function for integers, we define a small helper function abs.

String slicing in Go works similarly to Python slicing for this use case, allowing concise suffix comparisons after detecting the first mismatch.

Go strings are byte-based, but the problem constraints specify only letters and digits, so byte indexing is perfectly safe here.

Worked Examples

Example 1

Input:

s = "ab"
t = "acb"

Lengths:

  • m = 2
  • n = 3

Length difference is 1, so continue.

Step i j s[i] t[j] Action
1 0 0 a a Match, move both
2 1 1 b c Mismatch found

At the mismatch:

  • Lengths differ
  • Treat as insertion/deletion

Compare:

s[i:]   = "b"
t[j+1:] = "b"

They match, so return true.

Example 2

Input:

s = ""
t = ""

Lengths:

  • m = 0
  • n = 0

No mismatches occur because both strings are empty.

Final check:

m + 1 == n
0 + 1 == 0
False

Return false.

Additional Example

Input:

s = "cat"
t = "cut"
Step i j s[i] t[j] Action
1 0 0 c c Match
2 1 1 a u Mismatch

Lengths are equal, so this must be a replacement.

Compare:

s[i+1:] = "t"
t[j+1:] = "t"

They match, so return true.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is examined at most once
Space O(1) Only a few pointers and variables are used

The algorithm performs a single linear traversal through the strings. Even though suffix comparisons appear inside the mismatch handling, they collectively examine at most the remaining characters once, so the total complexity remains linear.

No auxiliary data structures proportional to input size are allocated, so the space complexity is constant.

Test Cases

solution = Solution()

assert solution.isOneEditDistance("ab", "acb") == True      # insertion
assert solution.isOneEditDistance("", "") == False          # zero edits
assert solution.isOneEditDistance("a", "") == True          # single deletion
assert solution.isOneEditDistance("", "a") == True          # single insertion
assert solution.isOneEditDistance("abc", "abc") == False    # identical strings
assert solution.isOneEditDistance("cat", "cut") == True     # single replacement
assert solution.isOneEditDistance("cat", "cats") == True    # insertion at end
assert solution.isOneEditDistance("cats", "cat") == True    # deletion at end
assert solution.isOneEditDistance("abc", "axc") == True     # replacement in middle
assert solution.isOneEditDistance("abc", "abdc") == True    # insertion in middle
assert solution.isOneEditDistance("abc", "adc") == True     # replacement
assert solution.isOneEditDistance("abc", "abcdx") == False  # length difference > 1
assert solution.isOneEditDistance("abc", "axyd") == False   # multiple edits
assert solution.isOneEditDistance("teacher", "bleacher") == False  # many edits
assert solution.isOneEditDistance("pale", "ple") == True    # deletion in middle
assert solution.isOneEditDistance("ple", "pale") == True    # insertion in middle
assert solution.isOneEditDistance("abc", "xbc") == True     # replacement at start
assert solution.isOneEditDistance("abc", "abx") == True     # replacement at end
assert solution.isOneEditDistance("abc", "axy") == False    # multiple replacements
Test Why
"ab", "acb" Valid insertion
"", "" Zero edits should fail
"a", "" Single deletion
"", "a" Single insertion
"abc", "abc" Identical strings
"cat", "cut" Single replacement
"cat", "cats" Extra trailing character
"cats", "cat" Removal of trailing character
"abc", "axc" Replacement in middle
"abc", "abdc" Insertion in middle
"abc", "adc" One replacement
"abc", "abcdx" Length difference too large
"abc", "axyd" Multiple edits required
"teacher", "bleacher" Large edit distance
"pale", "ple" Deletion inside string
"ple", "pale" Insertion inside string
"abc", "xbc" Replacement at beginning
"abc", "abx" Replacement at end
"abc", "axy" Multiple replacements

Edge Cases

Both Strings Are Empty

When s = "" and t = "", the strings are identical. A naive implementation might incorrectly return true because the strings are already equal. However, the problem requires exactly one edit, not zero edits.

The implementation handles this correctly because the loop finishes without mismatches, and the final condition checks whether the lengths differ by exactly one.

Length Difference Greater Than One

Cases like:

s = "abc"
t = "abcde"

cannot possibly be solved with a single edit.

Without an early length check, an implementation might waste time scanning the strings or accidentally allow multiple insertions.

The algorithm immediately returns false when:

abs(len(s) - len(t)) > 1

This prevents invalid cases from proceeding further.

Mismatch at the Last Character

Consider:

s = "abc"
t = "abx"

The strings match until the final position. Some incorrect implementations mishandle trailing mismatches because the loop terminates immediately afterward.

This solution correctly identifies the mismatch, recognizes that the strings have equal length, and compares the remaining suffixes:

s[i+1:] == t[j+1:]

Both suffixes are empty strings, so the replacement is valid.