Jobs

Interviews

Discussions

Check if One String Swap Can Make Strings Equal

Easy

DoorDash

3 views

Topics:

Strings

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Constraints:

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 and s2 consist of only lowercase English letters.

Try coding it in LeetCode

Check if One String Swap Can Make Strings Equal

Easy

DoorDash

3 views

Topics:

Strings

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Constraints:

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 and s2 consist of only lowercase English letters.

Try coding it in LeetCode

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:

Are the input strings guaranteed to be of the same length?
Can the input strings contain characters beyond the standard ASCII set, such as Unicode?
Are empty strings allowed as input, and if so, what should the function return?
If more than one swap could potentially make the strings equal, is any one of those swaps acceptable?
Are the strings case-sensitive, or should I treat uppercase and lowercase letters as equivalent?

Brute Force Solution

Approach

The goal is to see if we can make two strings identical by swapping just two letters in one of them. The brute force method involves trying every possible pair of letters to swap and then checking if the strings become equal.

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

Pick the first possible pair of letters in the first string to swap.
Swap those two letters.
See if the first string is now exactly the same as the second string.
If they are the same, we've found a solution and we're done.
If they aren't the same, undo the swap to put the first string back to how it originally was.
Now, pick the next possible pair of letters in the first string to swap.
Repeat the swapping, checking, and undoing process for every single possible pair of letters in the first string.
If, after checking every possible swap, we never found a match, then it's impossible to make the strings equal with just one swap.

Code Implementation

def can_make_equal_with_one_swap(first_string, second_string):
    string_length = len(first_string)

    for first_index_to_swap in range(string_length):
        for second_index_to_swap in range(first_index_to_swap + 1, string_length):

            # Create a list so that we can perform the swap
            first_string_as_list = list(first_string)

            # Perform the swap
            first_string_as_list[first_index_to_swap], first_string_as_list[second_index_to_swap] = \
                first_string_as_list[second_index_to_swap], first_string_as_list[first_index_to_swap]

            # Check if the strings are equal
            if "".join(first_string_as_list) == second_string:
                return True

            # This puts the first_string back into its original configuration
            first_string_as_list[first_index_to_swap], first_string_as_list[second_index_to_swap] = \
                first_string_as_list[second_index_to_swap], first_string_as_list[first_index_to_swap]

    # If no swaps resulted in equality return false
    return False

Big(O) Analysis

Time Complexity

O(n^2) – The described algorithm iterates through all possible pairs of characters within the first string of length n. To find all pairs, we have a nested loop structure. The outer loop iterates from the first character to the second-to-last character, and the inner loop iterates from the next character after the outer loop's current character to the last character. For each pair, we perform a swap and a comparison of the entire string. The pair finding process is dominant, resulting in approximately n * (n-1) / 2 comparisons, which simplifies to O(n^2).

Space Complexity

O(1) – The provided algorithm primarily performs in-place operations. It swaps characters within the first string and compares it to the second string. No auxiliary data structures, such as lists or hash maps, are used to store intermediate results or track visited states. The space used for temporary variables during the swap operation is constant and does not depend on the length of the input strings, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to see if swapping just two letters in one of the strings can make them identical. We'll pinpoint the differences between the strings and then check if a single swap can fix those differences.

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

First, find all the places where the two strings have different letters.
If there are no differences, the strings are already equal. However, if the strings are the same length, return true, otherwise return false because if one string is shorter than the other they could not be made the same with a single swap.
If there are exactly two differences, check if swapping the letters at those two positions in the first string makes it identical to the second string.
If swapping those two letters makes the strings equal, the answer is yes; otherwise, the answer is no.
If there are more than two differences, it's impossible to make the strings equal with just one swap, so the answer is no.

Code Implementation

def strings_can_be_made_equal_by_one_swap(string1, string2):
    string_length_1 = len(string1)
    string_length_2 = len(string2)
    
    if string_length_1 != string_length_2:
        return False
    
    difference_indices = []

    for index in range(string_length_1):
        if string1[index] != string2[index]:
            difference_indices.append(index)

    # Strings are equal, check lengths before returning.
    if not difference_indices:
        return True

    # More than two differences means one swap can't fix it.
    if len(difference_indices) != 2:
        return False

    index1, index2 = difference_indices

    # Verify if the swap makes strings equal.
    if string1[index1] == string2[index2] and string1[index2] == string2[index1]:
        return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the strings once to find the differing indices. This step takes O(n) time, where n is the length of the strings. Subsequently, it checks if there are zero, one, two or more differences and does a comparison or a swap operation. All these operations either take constant O(1) time or O(n) when comparing the strings after a swap. Because all operations are linear, the algorithm is dominated by the initial search for the differing indices, giving us a time complexity of O(n).

Space Complexity

O(1) – The algorithm identifies differing character indices. It stores at most two such indices. This storage requires a constant amount of extra space, irrespective of the input string lengths. Therefore, the auxiliary space used is constant and does not scale with the size of the input strings, denoted as N. Hence, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input strings	Return true if both are null/empty, false if one is null and the other isn't; consider empty strings as equal.
Strings of different lengths	Return false immediately, as a single swap cannot make strings of different lengths equal.
Strings are identical	Return true immediately, as zero swaps are considered valid and no swap is needed.
Strings differ by more than two characters	Return false immediately, as a single swap can only correct two mismatched characters.
Strings differ by exactly one character	Return false immediately, as a single swap requires two differing characters.
Strings have same characters but in different order (other than one swap)	A single swap won't fix this, so after finding two differences, perform the swap and if the strings don't match after the swap, return false.
Strings contain non-alphanumeric characters	The solution should work regardless of the character set as long as comparison operations are valid.
Strings are very long (performance)	The solution has linear time complexity O(n), which scales well with long strings.

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:

Are the input strings guaranteed to be of the same length?
Can the input strings contain characters beyond the standard ASCII set, such as Unicode?
Are empty strings allowed as input, and if so, what should the function return?
If more than one swap could potentially make the strings equal, is any one of those swaps acceptable?
Are the strings case-sensitive, or should I treat uppercase and lowercase letters as equivalent?

Brute Force Solution

Approach

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

Pick the first possible pair of letters in the first string to swap.
Swap those two letters.
See if the first string is now exactly the same as the second string.
If they are the same, we've found a solution and we're done.
If they aren't the same, undo the swap to put the first string back to how it originally was.
Now, pick the next possible pair of letters in the first string to swap.
Repeat the swapping, checking, and undoing process for every single possible pair of letters in the first string.
If, after checking every possible swap, we never found a match, then it's impossible to make the strings equal with just one swap.

Code Implementation

def can_make_equal_with_one_swap(first_string, second_string):
    string_length = len(first_string)

    for first_index_to_swap in range(string_length):
        for second_index_to_swap in range(first_index_to_swap + 1, string_length):

            # Create a list so that we can perform the swap
            first_string_as_list = list(first_string)

            # Perform the swap
            first_string_as_list[first_index_to_swap], first_string_as_list[second_index_to_swap] = \
                first_string_as_list[second_index_to_swap], first_string_as_list[first_index_to_swap]

            # Check if the strings are equal
            if "".join(first_string_as_list) == second_string:
                return True

            # This puts the first_string back into its original configuration
            first_string_as_list[first_index_to_swap], first_string_as_list[second_index_to_swap] = \
                first_string_as_list[second_index_to_swap], first_string_as_list[first_index_to_swap]

    # If no swaps resulted in equality return false
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find all the places where the two strings have different letters.
If there are no differences, the strings are already equal. However, if the strings are the same length, return true, otherwise return false because if one string is shorter than the other they could not be made the same with a single swap.
If there are exactly two differences, check if swapping the letters at those two positions in the first string makes it identical to the second string.
If swapping those two letters makes the strings equal, the answer is yes; otherwise, the answer is no.
If there are more than two differences, it's impossible to make the strings equal with just one swap, so the answer is no.

Code Implementation

def strings_can_be_made_equal_by_one_swap(string1, string2):
    string_length_1 = len(string1)
    string_length_2 = len(string2)
    
    if string_length_1 != string_length_2:
        return False
    
    difference_indices = []

    for index in range(string_length_1):
        if string1[index] != string2[index]:
            difference_indices.append(index)

    # Strings are equal, check lengths before returning.
    if not difference_indices:
        return True

    # More than two differences means one swap can't fix it.
    if len(difference_indices) != 2:
        return False

    index1, index2 = difference_indices

    # Verify if the swap makes strings equal.
    if string1[index1] == string2[index2] and string1[index2] == string2[index1]:
        return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input strings	Return true if both are null/empty, false if one is null and the other isn't; consider empty strings as equal.
Strings of different lengths	Return false immediately, as a single swap cannot make strings of different lengths equal.
Strings are identical	Return true immediately, as zero swaps are considered valid and no swap is needed.
Strings differ by more than two characters	Return false immediately, as a single swap can only correct two mismatched characters.
Strings differ by exactly one character	Return false immediately, as a single swap requires two differing characters.
Strings have same characters but in different order (other than one swap)	A single swap won't fix this, so after finding two differences, perform the swap and if the strings don't match after the swap, return false.
Strings contain non-alphanumeric characters	The solution should work regardless of the character set as long as comparison operations are valid.
Strings are very long (performance)	The solution has linear time complexity O(n), which scales well with long strings.