161. One Edit Distance

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 edit 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 1: One Pass Algorithm

First, we need to ensure that the string lengths are not too far apart.

If the length difference is 2 or more characters, then s and t cannot be one edit away from each other.

Next, assume s is always shorter than or the same length as t.

If not, we can always call isOneEditDistance(t, s) to handle the case where s is longer than t.

Now, we iterate through the characters of the strings and look for the first position where they differ.

If there are no differences in the first len(s) characters, there are two possible cases:

• The strings are equal.

• The strings are one edit away distance.

If a difference is found at position i where s[i] != t[i]:

• If the strings are of the same length, check if the substrings starting from i + 1 are equal.

• If t is one character longer than s, check if the substring starting from i in s is equal to the substring starting from i + 1 in t.

class Solution {

    public boolean isOneEditDistance(String s, String t) {
    
        int ns = s.length();
        int nt = t.length();
    
        // Ensure that s is shorter or equal in length to t
        if (ns > nt) {
            return isOneEditDistance(t, s);
        }
    
        // If the length difference is more than 1, they cannot be one edit apart
        if (nt - ns > 1) {
            return false;
        }
    
        // Iterate over the strings to find the first differing character
        for (int i = 0; i < ns; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                // If strings are of the same length, check remaining substrings
                if (ns == nt) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                } 
                // If t is one character longer than s, compare substrings after skipping one character in t
                else {
                    return s.substring(i).equals(t.substring(i + 1));
                }
            }
        }
    
        // If no differences found, the strings are one edit away only if t has one more character
        return (ns + 1 == nt);
    }
}

Complexity Analysis

Time Complexity: O(N) in the worst case when the string lengths are close enough (i.e., abs(ns - nt) <= 1), where N is the length of the longest string.

The algorithm scans through the strings once and performs substring operations if needed.

O(1) in the best case when the length difference is more than 1, as it immediately returns false.

Space Complexity: O(N) due to the substring operations.

Creating substrings requires additional space proportional to the length of the substring, which can be up to N.