We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

One Edit Distance

Number: 161

Difficulty: Medium

Paid? Yes

Companies: Yandex, Amazon, Snap, Meta, X, Uber

Problem Description

Given two strings s and t, determine if they are exactly one edit operation apart. An edit operation is defined as inserting exactly one character, deleting exactly one character, or replacing exactly one character in s to obtain t.

Key Insights

  • The difference in length between s and t must be at most 1.
  • When lengths are equal, the only possibility is that exactly one character is different (replacement).
  • When one string is longer by one character, the difference can be fixed by one insertion (or deletion in the other direction).
  • Use two pointers to compare corresponding characters and carefully handle the first difference.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the shorter string, as we traverse both strings at most once. Space Complexity: O(1), using only constant extra space.

Solution

The solution uses a two-pointer approach. First, we check if the length difference is greater than 1, in which case they cannot be one edit apart. For the two primary cases:

  1. When strings are of equal length, iterate through both strings and count the number of differing characters. There should be exactly one difference.
  2. When lengths differ by one, use pointers for both strings. Upon encountering a difference, increment the pointer for the longer string only and ensure that no previous difference has been encountered. If a second discrepancy is found, return false. The key is to handle the edge case where the difference is at the end of the string.

Code Solutions

# Function to check if two strings are one edit distance apart
def isOneEditDistance(s: str, t: str) -> bool:
    # Get lengths of both strings
    m, n = len(s), len(t)
    
    # The difference in length must not be greater than 1
    if abs(m - n) > 1:
        return False
    
    # Ensure s is the shorter string, or they are equal in length
    if m > n:
        return isOneEditDistance(t, s)
    
    # Initialize variables; found difference flag and indices for both strings
    found_difference = False
    i = j = 0
    
    while i < m and j < n:
        if s[i] != t[j]:
            # If a difference has already been found, return False
            if found_difference:
                return False
            found_difference = True
            # If lengths are equal, move both pointers
            if m == n:
                i += 1
        else:
            # If characters are the same, move the pointer in the shorter string
            i += 1
        # Always move pointer for longer string
        j += 1
    
    # If no difference was found during iteration, then one extra character at the end is the edit
    return found_difference or (j - i == 1)

# Example usage:
#print(isOneEditDistance("ab", "acb"))  # Output: True
← Back to All Questions