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.

Description Solution Video 4:20

161. One Edit Distance

Medium34.4% acceptance8 companiesPremium elsewhere, free here

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.

Asked at 8 companies

Twitter Snapchat Yandex Stripe Uber Meta Apple

Google

Topics

String Two Pointers

4:20

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

161. One Edit Distance

Asked at 8 companies

Topics

Similar problems