161. One Edit Distance - Solution & Explanation

The problem

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

Insert exactly one character into s to get t.
Delete exactly one character from s to get t.
Replace exactly one character of s with a different character to get t.

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Constraints:

0 <= s.length, t.length <= 10⁴
s and t consist of lowercase letters, uppercase letters, and digits.

Approach overview

Problem Overview: You are given two strings s and t. The goal is to determine whether they are exactly one edit apart. An edit can be an insertion, deletion, or replacement of a single character. If zero edits or more than one edit are required, the answer should be false.

Approach 1: Edit Distance Dynamic Programming (O(m*n) time, O(m*n) space)

A straightforward solution computes the classic edit distance between the two strings using dynamic programming. Create a DP table where dp[i][j] represents the minimum number of edits required to convert the first i characters of s into the first j characters of t. Each state considers insertion, deletion, or replacement. After filling the table, check whether the final edit distance equals exactly 1. This approach is simple and reusable for general edit distance problems, but it performs unnecessary work because the problem only cares about distance one. Time complexity is O(m*n) and space complexity is O(m*n), where m and n are the string lengths.

Approach 2: Discuss Different Cases with Two Pointers (O(n) time, O(1) space)

The optimal solution relies on careful case analysis and a linear scan using two pointers. First check the length difference. If the absolute difference exceeds one, the strings cannot be one edit apart. Otherwise iterate through both strings until the first mismatch appears. At that point three scenarios are possible: replacement when the lengths are equal, insertion into the shorter string, or deletion from the longer string. Instead of performing an explicit edit, advance the pointers according to the case and verify that the remaining substrings match.

This approach works because only one edit is allowed. Once a mismatch occurs, the rest of the characters must align perfectly. If no mismatch appears during the scan, the strings are one edit apart only when their lengths differ by exactly one (an extra trailing character). The algorithm processes each character once, giving O(n) time complexity and constant O(1) space. The logic relies heavily on careful pointer movement and efficient string comparison.

Recommended for interviews: Interviewers expect the linear two-pointer approach. The dynamic programming method demonstrates understanding of general edit distance, but it is overkill for this constraint. Showing the DP idea briefly and then optimizing to the case-based two pointer scan signals strong problem-solving ability and awareness of time complexity tradeoffs.

Solution

Let m represent the length of string s, and n represent the length of string t. We can assume that m is always greater than or equal to n.

If m-n > 1, return false directly;

Otherwise, iterate through s and t, if s[i] is not equal to t[i]:

If m neq n, compare s[i+1:] with t[i:], return true if they are equal, otherwise return false;
If m = n, compare s[i:] with t[i:], return true if they are equal, otherwise return false.

If the iteration ends, it means that all the characters of s and t that have been iterated are equal, at this time it needs to satisfy m=n+1.

The time complexity is O(m), where m is the length of string s. The space complexity is O(1).

Python

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        if len(s) < len(t):
            return self.isOneEditDistance(t, s)
        m, n = len(s), len(t)
        if m - n > 1:
            return False
        for i, c in enumerate(t):
            if c != s[i]:
                return s[i + 1 :] == t[i + 1 :] if m == n else s[i + 1 :] == t[i:]
        return m == n + 1

Java

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

C++

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

TypeScript

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

func isOneEditDistance(s string, t string) bool {
	m, n := len(s), len(t)
	if m < n {
		return isOneEditDistance(t, s)
	}
	if m-n > 1 {
		return false
	}
	for i := range t {
		if s[i] != t[i] {
			if m == n {
				return s[i+1:] == t[i+1:]
			}
			return s[i+1:] == t[i:]
		}
	}
	return m == n+1
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Edit Distance Dynamic Programming	O(m*n)	O(m*n)	When solving the general edit distance problem or when multiple edits must be computed
Case Analysis with Two Pointers	O(n)	O(1)	Best for checking if two strings differ by exactly one edit

Frequently asked questions

Is One Edit Distance easy or hard?

One Edit Distance is typically categorized as a Medium difficulty problem. The logic is simple once the three edit cases are identified, but many candidates struggle with edge cases such as equal strings or mismatches near the end.

One Edit Distance Python/Java solution

Most implementations follow the same pattern across languages: compare string lengths, scan until the first mismatch, and then verify the remaining substring alignment. Python, Java, C++, Go, and TypeScript versions all achieve O(n) time and O(1) space using the two pointer technique.

How to solve One Edit Distance in O(n)?

Check the length difference first. Iterate through both strings until a mismatch appears. If lengths are equal, skip one character in both strings (replacement case). If lengths differ by one, skip a character in the longer string (insertion or deletion case) and ensure the remaining substrings match.

What is the best approach for One Edit Distance?

The best approach uses a two pointer scan with case analysis. Compare both strings until the first mismatch appears, then handle replacement, insertion, or deletion depending on the length difference. This runs in O(n) time and O(1) space, which is optimal for this problem.

Is One Edit Distance asked at Google/Amazon/Meta?

One Edit Distance is a common string manipulation interview problem and variations have appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of string comparison, edge cases, and efficient pointer-based scanning.

What data structure is used in One Edit Distance?

The optimal solution primarily uses two pointers while iterating over strings. No complex data structures are needed, which keeps space complexity constant. The problem mainly tests string handling and pointer logic.

What is the time complexity of One Edit Distance?

The optimal solution runs in O(n) time where n is the length of the shorter string. Each character is compared at most once using two pointers. Space complexity remains O(1) since no additional data structures are required.

One Edit Distance solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

One Edit Distance solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems