Leetcode 859. Buddy Strings
Problem Explanation:
In this problem we have 2 strings A and B. We need to determine if we can swap any two letters in string A so that it results in being equal to string B.
To solve this, first check, if the length of A and B are not same then return False. If A is equal to B, then check if A has any duplicate letters by converting it to set and comparing sizes. If sizes are not same, it means A has duplicates and we can make a swap resulting in A equal to B hence return True.
Else it means A is not equal to B, so now find all indices where A and B differ. If there are exactly two indices where A and B differ and swapping the characters at these indices in A results in B, then return True else return False.
Example Walkthrough:
Let's take an example to understand this:
A = "ab", B = "ba"
Initially, compare length of A and B. If they are not equal return False. If they are equal proceed to next step.
Then compare if A and B are equal. If they are equal then check if A has any duplicates. If A has duplicates then return True, else False.
If A and B are not equal, Iterate over each letter in A and B, if any letter at same index in A and B are unequal then store this index and continue process for complete length of A.
If there are exactly two indices (let's say i and j) where A and B differ and swapping the charachters at indices i and j in A results in B then return True. If not return False.
1 ______i_______ ______j_______ 2 | | | |
A : "a" "b" -> "b" "a" B: "b" "a"
Python Solution:
1 2python 3class Solution: 4 def buddyStrings(self, A: str, B: str) -> bool: 5 if len(A) != len(B): 6 return False 7 if A == B: 8 return len(set(A)) < len(A) 9 else: 10 diff = [(a, b) for a, b in zip(A, B) if a != b] 11 return len(diff) == 2 and diff[0] == diff[1][::-1]
Java Solution:
1
2java
3class Solution {
4 public boolean buddyStrings(String A, String B) {
5 if (A.length() != B.length())
6 return false;
7 if (A.equals(B)) {
8 int[] count = new int[26];
9 for (int i = 0; i < A.length(); ++i)
10 count[A.charAt(i) - 'a']++;
11 for (int c: count)
12 if (c > 1) return true;
13 return false;
14 } else {
15 int first = -1, second = -1;
16 for (int i = 0; i < A.length(); ++i) {
17 if (A.charAt(i) != B.charAt(i)) {
18 if (first == -1)
19 first = i;
20 else if (second == -1)
21 second = i;
22 else
23 return false;
24 }
25 }
26 return (second != -1 && A.charAt(first) == B.charAt(second) && A.charAt(second) == B.charAt(first));
27 }
28 }
29}
Javascript Solution:
1
2javascript
3var buddyStrings = function(A, B) {
4 const len = A.length;
5 if(len != B.length) return false;
6
7 if(A === B){
8 const setA = new Set(A);
9 return setA.size < len;
10 } else {
11 let diff = [];
12 for(let i=0; i<len; ++i){
13 if(A[i] != B[i]) {
14 diff.push(i);
15 if(diff.length > 2) return false;
16 }
17 }
18 return diff.length == 2 && A[diff[0]] == B[diff[1]] && A[diff[1]] == B[diff[0]];
19 }
20};
C++ Solution:
1
2c++
3class Solution {
4public:
5 bool buddyStrings(string A, string B) {
6 if (A.length() != B.length())
7 return false;
8 if (A == B && set<char>(A.begin(), A.end()).size() < A.size())
9 return true;
10 vector<int> dif;
11 for (int i = 0; i < A.size(); ++i){
12 if (A[i] != B[i])
13 dif.push_back(i);
14 }
15 return dif.size() == 2 && A[dif[0]] == B[dif[1]] && A[dif[1]] == B[dif[0]];
16 }
17};
C# Solution:
1
2csharp
3public class Solution {
4 public bool BuddyStrings(string A, string B) {
5 if(A.Length != B.Length) return false;
6 if (A == B)
7 {
8 HashSet<char> unique_chars = new HashSet<char>(A);
9 if (unique_chars.Count < A.Length)
10 return true;
11 return false;
12 }
13 else
14 {
15 List<int> diff = new List<int>();
16 for (int i = 0; i < A.Length; i++)
17 {
18 if (A[i] != B[i])
19 diff.Add(i);
20 }
21 return (diff.Count == 2 && A[diff[0]] == B[diff[1]] && A[diff[1]] == B[diff[0]]);
22 }
23 }
24}
Go Solution:
1 2go 3import "sort" 4 5func buddyStrings(A string, B string) bool { 6 lenA, lenB := len(A), len(B) 7 if lenA != lenB { 8 return false 9 } 10 if A == B { 11 count := make([]int, 26) 12 for _, c := range A { 13 count[c-'a']++ 14 if count[c-'a'] > 1 { 15 return true 16 } 17 } 18 return false 19 } else { 20 diff := make([]byte, 0) 21 for i := 0; i < lenA; i++ { 22 if A[i] != B[i] { 23 diff = append(diff, A[i], B[i]) 24 25 } 26 } 27 return len(diff) == 4 && diff[0] == diff[3] && diff[1] == diff[2] 28 } 29}
Explanation of the Go Solution:
This Go solution follows the same logic we have discussed above in Python, Java, Javascript, C++, and C# solutions.
Initially, we check if A and B are of the same length, if not we return false
. If they are equal we move forward to check if A and B are identical. If they are identical A == B
, we also need to check if there are duplicate letters in A. For this, we can use a count
variable, to count occurrences of each character in A, if we find any character repeating more than 1 times, we have found duplicate, thus we return true
.
When A
and B
are not identical, we need to compare A and B. For every different set of characters at the same positions in both strings, we add them to the diff
slice. Finally, we expect diff
to be 4 (from A[i],B[i],A[j],B[j]) and on swapping A[i] with B[j], the result needs to be equal the B. In such a case, we would return true
.
The diff
is created so that it would look like the example: [A[i],B[i],A[j],B[j]]
, and we want to check A[i] == B[j]
and A[j] == B[i]
which means swapping i and j in A would result in B.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.