Buddy Strings - Leetcode Solution

Problem: Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Example: Input: A = "ab", B = "ba" Output: true

Input: A = "ab", B = "ab" Output: false

Input: A = "aa", B = "aa" Output: true

Input: A = "aaaaaaabc", B = "aaaaaaacb" Output: true

Input: A = "", B = "aa" Output: false

Approach: The idea is to check whether A and B are equal or not. If they are equal, then we need to check for duplicates in A. If there are duplicates, then we can swap any two same letters and the resulting string will be same as B. If there are no duplicates, then it is impossible to swap two letters and make it same as B.

If A and B are not equal, then we need to check the length of A and B. If the length of A and B is not same, then there is no way to swap two letters and make it same as B. If the length of A and B is same, then we need to check for the difference between A and B. If there are exactly two characters which are different in A and B, then it is possible to swap those two characters and make it same as B. Otherwise, it is impossible to swap two letters and make it same as B.

Solution:

class Solution { public: bool buddyStrings(string A, string B) { if(A.size() != B.size()) { return false; } if(A == B) { set<char> duplicates; for(char c : A) { if(duplicates.count(c)) { return true; } duplicates.insert(c); } return false; } else { int first = -1, second = -1; for(int i = 0; i < A.size(); i++) { if(A[i] != B[i]) { if(first == -1) { first = i; } else if(second == -1) { second = i; } else { return false; } } } if(first != -1 && second != -1) { return A[first] == B[second] && A[second] == B[first]; } return false; } } };

Time Complexity: O(n) Space Complexity: O(n)

1