Leetcode – Buddy Strings Solution in Python

Spread the love

The “Buddy Strings” problem is a popular algorithm challenge on the Leetcode platform. This problem tests the analytical thinking and implementation skills of a candidate. In this article, we’ll walk through the problem statement, analyze it, and then discuss various solutions.

Problem Statement

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

Constraints:

  • Both strings A and B have length in the range [1, 20000].
  • Strings A and B consist of lowercase letters from the set {'a', 'b', ..., 'z'}.

Examples:

  1. A = "ab", B = "ba" → Return true
  2. A = "ab", B = "ab" → Return false
  3. A = "aa", B = "aa" → Return true
  4. A = "aaaaaaabc", B = "aaaaaaacb" → Return true
  5. A = "", B = "aa" → Return false

Analysis

There are a few observations we can make:

  1. If A and B are of different lengths, they can’t be made identical by swapping two characters in A. So, return false immediately.
  2. If A and B are identical, then we can only return true if there’s at least one character that appears more than once in A, because that means we can swap the two identical characters to get an identical string.
  3. If A and B are not identical, then they must differ in exactly 2 places. Moreover, if we swap the differing characters in A, they should become identical to B.

Solution

Considering the above analysis, we can outline a solution:

  1. Compare the lengths of A and B.
  2. Identify the indices where A and B differ.
  3. Based on the number of differences, decide whether a swap can make A and B identical.

Python Code:

def buddyStrings(A: str, B: str) -> bool:
    # If lengths are different, return False
    if len(A) != len(B):
        return False
    
    # If A and B are the same, and any character in A has a frequency greater than 1
    # then return True
    if A == B:
        return len(A) - len(set(A)) > 0
    
    # Get the indices where A and B differ
    diff = [(a, b) for a, b in zip(A, B) if a != b]
    
    # If there are exactly 2 differences and the characters can be swapped to make A and B identical
    # return True
    return len(diff) == 2 and diff[0][0] == diff[1][1] and diff[0][1] == diff[1][0]

Complexity Analysis

  1. Time Complexity: The above solution checks the lengths and then compares the strings character by character. The time taken will be linear in terms of the string length, i.e., O(n).
  2. Space Complexity: We use a list called diff that stores the differences. In the worst case, this list can be as long as the string, i.e., O(n). The usage of set(A) also adds to the space complexity. But given the constraints, the maximum space required will be O(26) (considering all lowercase English alphabets), which is constant. Therefore, the overall space complexity is O(n).

Conclusion

The Buddy Strings problem tests the candidate’s ability to analyze string relationships and to perform string manipulations efficiently. Our solution leverages direct comparisons and observations based on the problem constraints to determine if one string can be transformed into another through a single swap. This problem emphasizes the importance of understanding the data and thinking through possible edge cases.

Leave a Reply