Jobs

Interviews

Discussions

Buddy Strings

Easy

Asked by:

14 views

Topics:

Strings

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

Constraints:

1 <= s.length, goal.length <= 2 * 10⁴
s and goal consist of lowercase letters.

Try coding it in LeetCode

Buddy Strings

Easy

Asked by:

14 views

Topics:

Strings

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

Constraints:

1 <= s.length, goal.length <= 2 * 10⁴
s and goal consist of lowercase 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 `s` and `goal` guaranteed to contain only lowercase English letters?
Can `s` and `goal` be empty strings or null? If so, what should I return?
What is the maximum length of the strings `s` and `goal`?
If `s` and `goal` are identical, is it permissible to swap identical characters within `s` to achieve `goal`?
Are `s` and `goal` case-sensitive? Should I assume they are already in the same case?

Brute Force Solution

Approach

The basic idea is to explore every single potential swap of two letters within the first word and see if it makes the first word identical to the second word. We will examine each possible swap and check if that swap leads to a solution.

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

Take the first word and consider all possible pairs of positions within it.
For each pair, swap the letters at those positions to create a new version of the first word.
Now, check if this newly created version of the first word is exactly the same as the second word.
If they are the same, we have found a solution; we can stop and report success.
If, after trying all possible swaps, we haven't found a match, then the words are not buddy strings, and we report failure.

Code Implementation

def buddy_strings_brute_force(first_word, second_word):
    word_length = len(first_word)
    if word_length != len(second_word):
        return False

    # Iterate through all possible pairs of indices
    for first_index in range(word_length):
        for second_index in range(first_index + 1, word_length):
            # Create a list to modify the first word
            modified_word_list = list(first_word)

            # Swap the letters at the two indices
            modified_word_list[first_index], modified_word_list[second_index] = \
                modified_word_list[second_index], modified_word_list[first_index]

            # Convert the list back to a string
            modified_word = "".join(modified_word_list)

            # Check if the modified word is equal to the second word
            if modified_word == second_word:
                return True

    # No swap resulted in a matching string
    return False

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through all possible pairs of positions in the first string, which has length n. For each element at index i, it potentially swaps it with all other elements at indices j where j ranges from i+1 to n-1. This nested iteration means that for each of the n positions, we potentially consider up to n-1 other positions. Therefore, the number of swaps and comparisons grow proportionally to approximately n * n/2, making the time complexity O(n^2).

Space Complexity

O(N) – The algorithm generates a new version of the first word by swapping characters. This new version of the word requires storing a copy of the input string, which has a length of N, where N is the length of the input string. Therefore, the auxiliary space needed to store this modified string is directly proportional to the length of the input string. Consequently, the space complexity is O(N).

Optimal Solution

Approach

To figure out if two strings can become each other with just one swap, we don't need to try every possible swap. The best method involves checking if simple conditions are met that would allow a swap to work, quickly deciding if a swap is possible, or certainly not.

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

First, quickly check if the strings are even the same length. If they are not, there's no way a swap could make them equal.
If the strings are identical, check if there's at least one character that appears more than once in the string. If so, swapping those identical characters will still result in the same string. This meets the problem criteria.
If the strings are not identical, count how many positions have different characters in the two strings. If this count is not exactly two, there's no way a single swap can make them equal.
If there are exactly two positions with different characters, check if swapping the characters at those two positions in the first string results in the second string. If it does, then the strings are buddy strings.

Code Implementation

def buddy_strings(first_string, second_string):
    if len(first_string) != len(second_string):
        return False

    if first_string == second_string:
        # Need to check for duplicate chars
        seen_characters = set()
        for character in first_string:
            if character in seen_characters:
                return True
            seen_characters.add(character)
        return False

    first_difference_index = -1
    second_difference_index = -1
    
    for index in range(len(first_string)):
        if first_string[index] != second_string[index]:
            if first_difference_index == -1:
                first_difference_index = index
            elif second_difference_index == -1:
                second_difference_index = index
            else:
                # More than two differences
                return False
    
    # Only proceed if there are exactly two indices where characters differ
    if first_difference_index != -1 and second_difference_index != -1:
        # Ensure swapping chars at difference indices produces the second string
        if (first_string[first_difference_index] == second_string[second_difference_index] and\
            first_string[second_difference_index] == second_string[first_difference_index]):
            return True
    
    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm first checks string lengths, which is O(1). If the strings are identical, it iterates through the string once to check for duplicate characters, which is O(n). If the strings are not identical, it iterates through the strings once to find the differing character positions, which is also O(n). Finally, it performs a constant time swap and comparison if exactly two differing positions exist, O(1). Therefore, the dominant operation is iterating through the string once, making the overall time complexity O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store indices and potentially a count of character occurrences. The space required does not scale with the input string length, N, as no auxiliary data structures like arrays or hash maps of size dependent on N are allocated. Therefore, the space complexity remains constant, regardless of the size of the input strings.

Edge Cases

Case	How to Handle
s or goal is null	Return false immediately as null strings cannot be compared.
s or goal is empty string	Return false if one is empty and the other is not, return true only if both are empty.
s and goal have different lengths	Return false immediately, as strings of different lengths cannot become equal by a single swap.
s and goal are identical	Check if s contains duplicate characters; if it does, a swap of the same character results in identical string, otherwise return false.
s and goal differ by more than two characters	Return false as only one swap is allowed.
Large strings (performance implications)	The algorithm should have O(n) time complexity making it appropriate for larger strings.
Strings with only 1 character	If the strings are identical and of length 1, and that single char must exist twice, then return true; if they are different, return false.
String containing Unicode characters	Ensure the character comparison handles unicode correctly, potentially requiring normalization.

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 `s` and `goal` guaranteed to contain only lowercase English letters?
Can `s` and `goal` be empty strings or null? If so, what should I return?
What is the maximum length of the strings `s` and `goal`?
If `s` and `goal` are identical, is it permissible to swap identical characters within `s` to achieve `goal`?
Are `s` and `goal` case-sensitive? Should I assume they are already in the same case?

Brute Force Solution

Approach

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

Take the first word and consider all possible pairs of positions within it.
For each pair, swap the letters at those positions to create a new version of the first word.
Now, check if this newly created version of the first word is exactly the same as the second word.
If they are the same, we have found a solution; we can stop and report success.
If, after trying all possible swaps, we haven't found a match, then the words are not buddy strings, and we report failure.

Code Implementation

def buddy_strings_brute_force(first_word, second_word):
    word_length = len(first_word)
    if word_length != len(second_word):
        return False

    # Iterate through all possible pairs of indices
    for first_index in range(word_length):
        for second_index in range(first_index + 1, word_length):
            # Create a list to modify the first word
            modified_word_list = list(first_word)

            # Swap the letters at the two indices
            modified_word_list[first_index], modified_word_list[second_index] = \
                modified_word_list[second_index], modified_word_list[first_index]

            # Convert the list back to a string
            modified_word = "".join(modified_word_list)

            # Check if the modified word is equal to the second word
            if modified_word == second_word:
                return True

    # No swap resulted in a matching string
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, quickly check if the strings are even the same length. If they are not, there's no way a swap could make them equal.
If the strings are identical, check if there's at least one character that appears more than once in the string. If so, swapping those identical characters will still result in the same string. This meets the problem criteria.
If the strings are not identical, count how many positions have different characters in the two strings. If this count is not exactly two, there's no way a single swap can make them equal.
If there are exactly two positions with different characters, check if swapping the characters at those two positions in the first string results in the second string. If it does, then the strings are buddy strings.

Code Implementation

def buddy_strings(first_string, second_string):
    if len(first_string) != len(second_string):
        return False

    if first_string == second_string:
        # Need to check for duplicate chars
        seen_characters = set()
        for character in first_string:
            if character in seen_characters:
                return True
            seen_characters.add(character)
        return False

    first_difference_index = -1
    second_difference_index = -1
    
    for index in range(len(first_string)):
        if first_string[index] != second_string[index]:
            if first_difference_index == -1:
                first_difference_index = index
            elif second_difference_index == -1:
                second_difference_index = index
            else:
                # More than two differences
                return False
    
    # Only proceed if there are exactly two indices where characters differ
    if first_difference_index != -1 and second_difference_index != -1:
        # Ensure swapping chars at difference indices produces the second string
        if (first_string[first_difference_index] == second_string[second_difference_index] and\
            first_string[second_difference_index] == second_string[first_difference_index]):
            return True
    
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
s or goal is null	Return false immediately as null strings cannot be compared.
s or goal is empty string	Return false if one is empty and the other is not, return true only if both are empty.
s and goal have different lengths	Return false immediately, as strings of different lengths cannot become equal by a single swap.
s and goal are identical	Check if s contains duplicate characters; if it does, a swap of the same character results in identical string, otherwise return false.
s and goal differ by more than two characters	Return false as only one swap is allowed.
Large strings (performance implications)	The algorithm should have O(n) time complexity making it appropriate for larger strings.
Strings with only 1 character	If the strings are identical and of length 1, and that single char must exist twice, then return true; if they are different, return false.
String containing Unicode characters	Ensure the character comparison handles unicode correctly, potentially requiring normalization.