Solution


Approach 1: Enumerate Cases

Intuition

Let's say i is matched if A[i] == B[i], otherwise i is unmatched. A buddy string has almost all matches, because a swap only affects two indices.

If swapping A[i] and A[j] would demonstrate that A and B are buddy strings, then A[i] == B[j] and A[j] == B[i]. That means among the four free variables A[i], A[j], B[i], B[j], there are only two cases: either A[i] == A[j] or not.

Algorithm

Let's work through the cases.

In the case A[i] == A[j] == B[i] == B[j], then the strings A and B are equal. So if A == B, we should check each index i for two matches with the same value.

In the case A[i] == B[j], A[j] == B[i], (A[i] != A[j]), the rest of the indices match. So if A and B have only two unmatched indices (say i and j), we should check that the equalities A[i] == B[j] and A[j] == B[i] hold.

Complexity Analysis

  • Time Complexity: , where is the length of A and B.

  • Space Complexity: .


Analysis written by: @awice.