One Edit Distance

One Edit Distance

What is this problem about?

The One Edit Distance problem asks whether two strings are exactly one edit operation apart — where one edit means either inserting, deleting, or replacing a single character. This coding problem uses a two-pointer comparison with careful case handling. The two pointers and string interview pattern is directly demonstrated.

Why is this asked in interviews?

Uber, Meta, Twitter, Stripe, and Google ask this as a practical string comparison problem. It tests careful edge case handling and clean two-pointer logic. Unlike edit distance (which counts all operations), this only asks for a yes/no answer for exactly 1 operation.

Algorithmic pattern used

Two-pointer with mismatch handling. If |len(s) - len(t)| > 1, return false. If lengths equal: count mismatches — exactly 1 mismatch = valid (replace). If lengths differ by 1: advance pointers — on a mismatch, advance the longer string's pointer and check remaining characters must match exactly.

Example explanation

s="abc", t="abdc". len difference = 1 (insert case).

• Compare: 'a'='a', 'b'='b'. Mismatch: 'c' vs 'd'. Advance t's pointer.
• Compare s[2]='c' with t[3]='c'. Match. Continue. Both exhausted. Exactly one insert needed → true.

s="abc", t="abd". len equal. Mismatches: 'c' vs 'd' → 1 mismatch (replace). → true. s="abc", t="xyz". 3 mismatches → false.

Common mistakes candidates make

• Checking after encountering the first mismatch that remaining characters match exactly (critical step).
• Not handling the case where one string is a prefix of the other + one character.
• Returning true when lengths differ by more than 1.
• Not correctly identifying replace vs insert vs delete.

Interview preparation tip

One Edit Distance is a focused variant of edit distance. The key implementation detail: after finding the first mismatch, shift the pointer for the longer string and verify remaining characters match exactly. Two sub-cases: equal length (replace only) and length-difference-1 (insert/delete). Practice this problem until the mismatch-then-verify logic is fluent — it's a common follow-up to edit distance questions at companies like Meta and Uber.