How to Check If Two Strings are Buddy Strings?

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 1:
Input: A = “ab”, B = “ba”

Output: true
Example 2:

Input: A = “ab”, B = “ab”
Output: false
Example 3:

Input: A = “aa”, B = “aa”
Output: true
Example 4:

Input: A = “aaaaaaabc”, B = “aaaaaaacb”
Output: true
Example 5:

Input: A = “”, B = “aa”
Output: false

Note:
0 <= A.length <= 20000
0 <= B.length <= 20000
A and B consist only of lowercase letters.

Buddy Strings Algorithm in C++

The algorithm to determine if two strings are buddy can be done via enumerating the cases. First, we have to compute the number of differences between given two strings.

• If both strings are of different lengths or one string’s length is length smaller than 2, they can’t be buddy strings.
• If no differences are found (they are equal), they still can be buddys if the string contains at least two idential characters (lowercase). The same letters can be swapped.
• If there are more than 2 differences, they simply can’t be buddy.
• If there are 2 differences, they are buddy strings if after swapped, one equals to another.
• If there is 1 difference, they are not buddys

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool buddyStrings(string A, string B) {
        if (A.size() != B.size()) return false;
        if (A.size() < = 1) return false;
        vector<int> idx;
        bool dup = false;
        int count[26] = {0};
        for (int i = 0; i < A.size(); ++ i) {
            if (A[i] != B[i]) {
                idx.push_back(i);
                if (idx.size() > 2) {
                    return false;
                }
            }
            if (++count[A[i] - 97] > 1) dup = true;
        }
        if (idx.size() == 1) return false;
        if (idx.size() == 2) {
            return (A[idx[0]] == B[idx[1]]) && (A[idx[1]] == B[idx[0]]);
        }                        
        return dup;
    }
};

class Solution {
public:
    bool buddyStrings(string A, string B) {
        if (A.size() != B.size()) return false;
        if (A.size() < = 1) return false;
        vector<int> idx;
        bool dup = false;
        int count[26] = {0};
        for (int i = 0; i < A.size(); ++ i) {
            if (A[i] != B[i]) {
                idx.push_back(i);
                if (idx.size() > 2) {
                    return false;
                }
            }
            if (++count[A[i] - 97] > 1) dup = true;
        }
        if (idx.size() == 1) return false;
        if (idx.size() == 2) {
            return (A[idx[0]] == B[idx[1]]) && (A[idx[1]] == B[idx[0]]);
        }                        
        return dup;
    }
};

We can push the indice of differences to std::vector when we iterative the strings. The time complexity is O(N) as we have to go through each lowercase of the given string. The space complexity for above C++ implementation is O(1) as we break after finding more than 2 differences so no more pushes to the vector.

--EOF (The Ultimate Computing & Technology Blog) --