One Edit Distance

medium string two pointers

Problem

Given two strings s and t, return true if they are exactly one edit (insert, delete, or replace one character) away from each other. Equal strings count as zero edits — they are not one-edit-distance.

Inputs = "ab", t = "acb"

Outputtrue

Walk together: 'a'='a'. Mismatch at index 1: 'b' vs 'c'. Lengths differ by 1 → try inserting; remaining "b" matches. One edit.

def is_one_edit_distance(s, t):
    if len(s) > len(t):
        return is_one_edit_distance(t, s)
    if len(t) - len(s) > 1:
        return False
    for i in range(len(s)):
        if s[i] != t[i]:
            if len(s) == len(t):
                return s[i + 1:] == t[i + 1:]
            return s[i:] == t[i + 1:]
    return len(t) == len(s) + 1

function isOneEditDistance(s, t) {
  if (s.length > t.length) return isOneEditDistance(t, s);
  if (t.length - s.length > 1) return false;
  for (let i = 0; i < s.length; i++) {
    if (s[i] !== t[i]) {
      if (s.length === t.length) return s.slice(i + 1) === t.slice(i + 1);
      return s.slice(i) === t.slice(i + 1);
    }
  }
  return t.length === s.length + 1;
}

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s.length() > t.length()) return isOneEditDistance(t, s);
        if (t.length() - s.length() > 1) return false;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (s.length() == t.length()) return s.substring(i + 1).equals(t.substring(i + 1));
                return s.substring(i).equals(t.substring(i + 1));
            }
        }
        return t.length() == s.length() + 1;
    }
}

bool isOneEditDistance(string s, string t) {
    if (s.size() > t.size()) return isOneEditDistance(t, s);
    if (t.size() - s.size() > 1) return false;
    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] != t[i]) {
            if (s.size() == t.size()) return s.substr(i + 1) == t.substr(i + 1);
            return s.substr(i) == t.substr(i + 1);
        }
    }
    return t.size() == s.size() + 1;
}

Explanation

Two strings are "one edit apart" if a single replace, insert, or delete turns one into the other. The clever part is that we only ever need to find the first place they differ and check what happens after that.

First we make sure s is the shorter string (swapping by recursion if needed) and bail out early: if the lengths differ by more than 1, no single edit can bridge them, so return false.

Then we walk both strings together. At the first mismatch at index i there are two cases. If the lengths are equal, the only allowed move is a replace, so we check that the rest matches: s[i+1:] == t[i+1:]. If the lengths differ by one, the move is an insert/delete, so we line up s[i:] against t[i+1:] (skipping the extra character in t).

If we never find a mismatch while scanning, the strings share a common prefix. In that case they are one edit apart only if t has exactly one extra trailing character, i.e. len(t) == len(s) + 1.

Example: s = "ab", t = "acb". They match at index 0 ('a'). At index 1, 'b' vs 'c' mismatches; lengths differ by 1, so we compare s[1:]="b" with t[2:]="b" — equal, so the answer is true.

Time: O(n) Space: O(n)