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.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ