Jobs

Interviews

Discussions

One Edit Distance

Medium

Snap

1 view

Topics:

StringsTwo Pointers

Given two strings s and t, determine if they are both one edit distance apart.

Note:

There are three possible edits to transform one string to another:

Insert a character into a string
Delete a character from a string
Replace a character in a string

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 need exactly one edit to transform one string into another.

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "a"
Output: true

Example 5:

Input: s = "abc", t = "adc"
Output: true

Constraints:

0 <= s.length <= 10⁴
0 <= t.length <= 10⁴
s and t consist of lower-case letters, upper-case letters and/or digits.

One Edit Distance

Medium

Snap

1 view

Topics:

StringsTwo Pointers

Given two strings s and t, determine if they are both one edit distance apart.

Note:

There are three possible edits to transform one string to another:

Insert a character into a string
Delete a character from a string
Replace a character in a string

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 need exactly one edit to transform one string into another.

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "a"
Output: true

Example 5:

Input: s = "abc", t = "adc"
Output: true

Constraints:

0 <= s.length <= 10⁴
0 <= t.length <= 10⁴
s and t consist of lower-case letters, upper-case letters and/or digits.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings s and t be null or empty?
Are s and t case-sensitive? Should I treat 'a' and 'A' as different characters?
What is the maximum length of the input strings s and t?
If the strings are identical, is that considered zero edits and should I return false?
By 'one edit' do you strictly mean *exactly* one edit, or is zero edits acceptable?

Brute Force Solution

Approach

The brute force method for determining if two strings are within one edit distance of each other involves exploring all possible single edits on each string. This means trying every possible insertion, deletion, and replacement to see if any of those changes makes the strings equal. If at least one of these edits results in the two strings being identical, then they are indeed one edit distance away.

Here's how the algorithm would work step-by-step:

Consider the first string. Imagine adding one character at every possible position, including the beginning and the end, and compare each of those new strings to the second string.
Next, try removing one character from every possible position in the first string, and compare each of those new strings to the second string.
Then, try replacing each character in the first string with every possible other character (for example a-z). Compare each of those new strings to the second string.
Repeat the same process on the second string: try adding, deleting, and replacing characters, and compare each of those new strings to the first string.
If, at any point, any of the modified strings becomes identical to the other original string, you've found a single edit that makes them equal.
If you exhaust all these possibilities of adding, deleting, or replacing characters in either of the strings and you never find a match, then the two strings are not one edit distance away from each other.

Code Implementation

def is_one_edit_distance_brute_force(first_string, second_string):
    string_length_first = len(first_string)
    string_length_second = len(second_string)

    # Check if adding a character to first_string makes it equal to second_string
    for index in range(string_length_first + 1):
        modified_string = first_string[:index] + 'x' + first_string[index:]
        if modified_string == second_string:
            return True

    # Check if deleting a character from first_string makes it equal to second_string
    for index in range(string_length_first):
        modified_string = first_string[:index] + first_string[index+1:]
        if modified_string == second_string:
            return True

    # Check if replacing a character in first_string makes it equal to second_string
    for index in range(string_length_first):
        for char_code in range(ord('a'), ord('z') + 1):
            replacement_character = chr(char_code)
            modified_string = first_string[:index] + replacement_character + first_string[index+1:]

            if modified_string == second_string:
                return True

    # Now, repeat the process for second_string to check edits to second_string
    for index in range(string_length_second + 1):
        modified_string = second_string[:index] + 'x' + second_string[index:]
        if modified_string == first_string:
            return True

    for index in range(string_length_second):
        modified_string = second_string[:index] + second_string[index+1:]
        if modified_string == first_string:
            return True

    # Replacing characters in second_string
    for index in range(string_length_second):
        for char_code in range(ord('a'), ord('z') + 1):
            replacement_character = chr(char_code)
            modified_string = second_string[:index] + replacement_character + second_string[index+1:]

            if modified_string == first_string:
                return True

    # Exhausted all options, so return False
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm explores all possible single edits (insertions, deletions, replacements) on both strings. For a string of length n, inserting a character involves n+1 possible positions. Deleting involves n positions. Replacing involves n positions, and potentially up to a constant number of replacement characters. Comparing strings after each modification takes O(n) time. Since these modifications and comparisons are nested within loops iterating through the string lengths, the overall time complexity becomes O(n * n). Therefore, the dominant factor leading to the complexity is the string comparisons after the edits, resulting in O(n^2).

Space Complexity

O(1) – The provided brute force solution described involves generating modified strings (by inserting, deleting, or replacing characters) and comparing them to the original strings. While the algorithm implicitly calculates these modified strings, the description doesn't specify explicitly storing all possible modified strings simultaneously in memory. It focuses on iterative comparison. The process only requires storing a few index variables and potentially a single modified string at a time for comparison, and since the size of these variables is independent of the input string lengths, the space used remains constant. Thus the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to quickly determine if two words are nearly identical, differing by only one edit. The smart strategy is to identify the first difference and then focus our attention solely on the remaining parts of the words. This avoids unnecessary comparisons when a difference is already found.

Here's how the algorithm would work step-by-step:

First, check if the lengths of the two words are very different. If the lengths differ by more than one, they can't be one edit away, so we're done.
Now, go through both words character by character, comparing them.
If you find a character that's different, there are three possibilities to consider: either a character was inserted, removed, or replaced.
If the words are the same length, it means a character was replaced. Check if the rest of the words are identical after that replacement.
If one word is longer than the other, it means a character was inserted or deleted. Skip the different character in the longer word, and see if the rest of the words match perfectly.
If, after the first different character, the remaining parts of the words match (accounting for insertions/deletions/replacements), then the words are one edit away.
If you get to the end of both words without finding any differences, check if they are the same length. If they are the same, no edits were needed, so they aren't one edit away. If they differ by one, then a single insertion or deletion occurred.

Code Implementation

def is_one_edit_distance(first_word, second_word):
    length_difference = abs(len(first_word) - len(second_word))
    if length_difference > 1:
        return False

    first_word_length = len(first_word)
    second_word_length = len(second_word)

    index_first_word = 0
    index_second_word = 0
    difference_found = False

    while index_first_word < first_word_length and index_second_word < second_word_length:
        if first_word[index_first_word] != second_word[index_second_word]:
            # Mark that a difference has been found
            difference_found = True

            if first_word_length == second_word_length:
                # Handles the replacement case
                index_first_word += 1
                index_second_word += 1
            elif first_word_length > second_word_length:
                # Handles deletion from first_word
                index_first_word += 1
            else:
                # Handles insertion into first_word
                index_second_word += 1
        else:
            index_first_word += 1
            index_second_word += 1

        if difference_found:
            remaining_first_word = first_word[index_first_word:]
            remaining_second_word = second_word[index_second_word:]

            # After the difference, remaining parts should match
            if remaining_first_word != remaining_second_word:
                return False
            else:
                return True

    # No differences found until the end.
    if not difference_found:
        # Need to check if a single insertion/deletion occurred.
        return length_difference == 1

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the characters of the two strings, comparing them one by one. In the worst-case scenario, it might need to compare all characters of the shorter string. After finding the first difference, it compares the remaining substrings. Therefore, the dominant operation is the single pass through the string, which takes linear time proportional to the length of the shorter string. Thus, the time complexity is O(n), where n is the length of the shorter string.

Space Complexity

O(1) – The algorithm iterates through the input strings using index variables, and performs direct character comparisons. It does not utilize any auxiliary data structures such as lists, hash maps, or sets to store intermediate results or track visited elements. Therefore, the space used remains constant irrespective of the lengths of the input strings. Consequently, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Both strings are null	Treat as zero edits, thus should return false since zero is not one.
One string is null, the other is not empty	If one string is null and the other has length 1, return true; otherwise return false.
Both strings are empty	Return false as zero edits do not satisfy 'one edit distance'.
Strings are identical	Return false because they are zero edits away from each other.
Length difference is greater than 1	Return false immediately since more than one insertion/deletion would be required.
Strings have the same length, but differ by more than one character	Return false since more than one replacement is needed.
Strings have very long length (potential performance issue)	The algorithm should iterate linearly through the strings, so it scales as O(n).
Strings contain unicode characters	Character comparison should handle unicode characters correctly in most languages.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings s and t be null or empty?
Are s and t case-sensitive? Should I treat 'a' and 'A' as different characters?
What is the maximum length of the input strings s and t?
If the strings are identical, is that considered zero edits and should I return false?
By 'one edit' do you strictly mean *exactly* one edit, or is zero edits acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the first string. Imagine adding one character at every possible position, including the beginning and the end, and compare each of those new strings to the second string.
Next, try removing one character from every possible position in the first string, and compare each of those new strings to the second string.
Then, try replacing each character in the first string with every possible other character (for example a-z). Compare each of those new strings to the second string.
Repeat the same process on the second string: try adding, deleting, and replacing characters, and compare each of those new strings to the first string.
If, at any point, any of the modified strings becomes identical to the other original string, you've found a single edit that makes them equal.
If you exhaust all these possibilities of adding, deleting, or replacing characters in either of the strings and you never find a match, then the two strings are not one edit distance away from each other.

Code Implementation

def is_one_edit_distance_brute_force(first_string, second_string):
    string_length_first = len(first_string)
    string_length_second = len(second_string)

    # Check if adding a character to first_string makes it equal to second_string
    for index in range(string_length_first + 1):
        modified_string = first_string[:index] + 'x' + first_string[index:]
        if modified_string == second_string:
            return True

    # Check if deleting a character from first_string makes it equal to second_string
    for index in range(string_length_first):
        modified_string = first_string[:index] + first_string[index+1:]
        if modified_string == second_string:
            return True

    # Check if replacing a character in first_string makes it equal to second_string
    for index in range(string_length_first):
        for char_code in range(ord('a'), ord('z') + 1):
            replacement_character = chr(char_code)
            modified_string = first_string[:index] + replacement_character + first_string[index+1:]

            if modified_string == second_string:
                return True

    # Now, repeat the process for second_string to check edits to second_string
    for index in range(string_length_second + 1):
        modified_string = second_string[:index] + 'x' + second_string[index:]
        if modified_string == first_string:
            return True

    for index in range(string_length_second):
        modified_string = second_string[:index] + second_string[index+1:]
        if modified_string == first_string:
            return True

    # Replacing characters in second_string
    for index in range(string_length_second):
        for char_code in range(ord('a'), ord('z') + 1):
            replacement_character = chr(char_code)
            modified_string = second_string[:index] + replacement_character + second_string[index+1:]

            if modified_string == first_string:
                return True

    # Exhausted all options, so return False
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the lengths of the two words are very different. If the lengths differ by more than one, they can't be one edit away, so we're done.
Now, go through both words character by character, comparing them.
If you find a character that's different, there are three possibilities to consider: either a character was inserted, removed, or replaced.
If the words are the same length, it means a character was replaced. Check if the rest of the words are identical after that replacement.
If one word is longer than the other, it means a character was inserted or deleted. Skip the different character in the longer word, and see if the rest of the words match perfectly.
If, after the first different character, the remaining parts of the words match (accounting for insertions/deletions/replacements), then the words are one edit away.
If you get to the end of both words without finding any differences, check if they are the same length. If they are the same, no edits were needed, so they aren't one edit away. If they differ by one, then a single insertion or deletion occurred.

Code Implementation

def is_one_edit_distance(first_word, second_word):
    length_difference = abs(len(first_word) - len(second_word))
    if length_difference > 1:
        return False

    first_word_length = len(first_word)
    second_word_length = len(second_word)

    index_first_word = 0
    index_second_word = 0
    difference_found = False

    while index_first_word < first_word_length and index_second_word < second_word_length:
        if first_word[index_first_word] != second_word[index_second_word]:
            # Mark that a difference has been found
            difference_found = True

            if first_word_length == second_word_length:
                # Handles the replacement case
                index_first_word += 1
                index_second_word += 1
            elif first_word_length > second_word_length:
                # Handles deletion from first_word
                index_first_word += 1
            else:
                # Handles insertion into first_word
                index_second_word += 1
        else:
            index_first_word += 1
            index_second_word += 1

        if difference_found:
            remaining_first_word = first_word[index_first_word:]
            remaining_second_word = second_word[index_second_word:]

            # After the difference, remaining parts should match
            if remaining_first_word != remaining_second_word:
                return False
            else:
                return True

    # No differences found until the end.
    if not difference_found:
        # Need to check if a single insertion/deletion occurred.
        return length_difference == 1

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both strings are null	Treat as zero edits, thus should return false since zero is not one.
One string is null, the other is not empty	If one string is null and the other has length 1, return true; otherwise return false.
Both strings are empty	Return false as zero edits do not satisfy 'one edit distance'.
Strings are identical	Return false because they are zero edits away from each other.
Length difference is greater than 1	Return false immediately since more than one insertion/deletion would be required.
Strings have the same length, but differ by more than one character	Return false since more than one replacement is needed.
Strings have very long length (potential performance issue)	The algorithm should iterate linearly through the strings, so it scales as O(n).
Strings contain unicode characters	Character comparison should handle unicode characters correctly in most languages.