One Edit Distance - Solution & Explanation

Problem Overview: Given two strings s and t, determine whether they are exactly one edit apart. An edit is defined as inserting a character, deleting a character, or replacing a character. If zero edits or more than one edit are required, the result should be false.

Approach 1: Generate Possible Edits (Brute Force) (Time: O(n^2), Space: O(n))

The straightforward idea is to simulate all possible single edits on one string and check whether any result matches the other string. For each index, try three operations: delete the character, replace it with every possible character, or insert a new character. Each generated candidate is compared with the target string. This works conceptually but quickly becomes inefficient because constructing new strings repeatedly leads to quadratic behavior. It mainly helps build intuition about the three allowed operations.

Approach 2: Edit Distance Dynamic Programming (Time: O(m * n), Space: O(m * n))

This approach computes the classic edit distance between two strings using dynamic programming. A dp[i][j] table stores the minimum edits needed to convert the first i characters of s into the first j characters of t. Transitions handle insert, delete, and replace operations. After filling the table, check whether the final edit distance equals exactly 1. While correct and easy to reason about, this solution is overkill because the problem only asks whether the distance is one, not the full edit distance.

Approach 3: Two Pointers String Scan (Optimal) (Time: O(n), Space: O(1))

The optimal solution relies on a single pass using two pointers. If the length difference between the strings is greater than one, return false immediately. Otherwise iterate through both strings until the first mismatch appears. When characters differ, simulate the correct operation based on lengths: move both pointers for replacement, move the longer string pointer for insertion/deletion. After this point the remaining substrings must match exactly. This works because only one edit is allowed, so the strings can diverge at most once.

The algorithm mostly performs a linear comparison of characters from both strings and carefully handles the three edit scenarios. It uses constant extra memory and fits naturally with string manipulation patterns common in interview questions.

Recommended for interviews: Start by explaining the three edit operations and why generating edits or using full dynamic programming works conceptually. Then move to the optimal two pointers scan. Interviewers typically expect the O(n) approach because it demonstrates careful reasoning about string length differences and pointer movement rather than brute-force simulation.