Skip to main content
Talentd

One Edit Distance - Solution & Explanation

MediumPremiumFree on FleetCodeTwo PointersString8 min readAsked at: Apple, Meta, Uber +5
Practice this problem

Problem Statement

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 <= 104
  • 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

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

Video Solution

161. One Edit Distance (LeetCode) • hakunamatasq • 2,580 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice One Edit Distance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Edit Distance