LeetCode 859: Buddy Strings

Problem Restatement

We are given two strings:

s
goal

We need to return True if we can swap exactly two letters in s so that the result becomes equal to goal.

A swap means choosing two different indices i and j, then exchanging:

s[i]
s[j]

If no such swap exists, return False.

Input and Output

Function shape:

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        ...

Examples

Example 1:

s = "ab"
goal = "ba"

Swap the two characters in s:

"ab" -> "ba"

So the answer is:

True

Example 2:

s = "ab"
goal = "ab"

The strings are already equal, but we must still perform one swap.

The only possible swap gives:

"ab" -> "ba"

That does not equal goal, so the answer is:

False

Example 3:

s = "aa"
goal = "aa"

The strings are already equal.

We can swap the two equal characters:

"aa" -> "aa"

The string stays the same, but a valid swap was performed.

So the answer is:

True

First Thought: Simulate Every Swap

One direct solution is to try every pair of indices.

For every pair (i, j):

1. Swap s[i] and s[j].
2. Check whether the result equals goal.

This is correct, but it costs too much.

If the string length is n, there are about:

n * (n - 1) / 2

possible swaps.

Building or checking strings for every swap can make this too slow.

Key Insight

A single swap can only change two positions.

So compare s and goal.

There are three important cases.

First, if the lengths are different, the answer is immediately False.

Second, if s and goal are equal, we still need to make one swap. This is possible only if s has a duplicate character. Swapping two equal letters keeps the string unchanged.

For example:

s = "aa"
goal = "aa"

works, but:

s = "ab"
goal = "ab"

does not work.

Third, if s and goal are different, then they must differ at exactly two positions.

Suppose the mismatched indices are i and j.

Swapping s[i] and s[j] works only if:

s[i] == goal[j]
s[j] == goal[i]

Algorithm

First, check length:

if len(s) != len(goal):
    return False

If the strings are equal:

1. Check whether any character appears at least twice.
2. If yes, return True.
3. Otherwise, return False.

If the strings are not equal:

1. Collect all indices where s[i] != goal[i].
2. If the number of mismatches is not exactly 2, return False.
3. Let those two indices be i and j.
4. Return whether swapping those two characters would match goal.

Correctness

If the lengths are different, no swap inside s can change its length, so returning False is correct.

If s == goal, the only way to perform a swap and keep the string unchanged is to swap two equal characters. Such a swap exists exactly when some character appears at least twice. Therefore, the duplicate check is correct.

Now suppose s != goal.

A swap changes only two positions. Therefore, if there are fewer or more than two mismatched positions, one swap cannot transform s into goal.

If there are exactly two mismatched positions i and j, then the swap works exactly when the character at s[i] belongs at goal[j], and the character at s[j] belongs at goal[i].

The algorithm checks exactly these conditions, so it returns the correct result.

Complexity

Here, n is the length of s.

Implementation

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False

        if s == goal:
            return len(set(s)) < len(s)

        diff = []

        for i in range(len(s)):
            if s[i] != goal[i]:
                diff.append(i)

        if len(diff) != 2:
            return False

        i, j = diff

        return s[i] == goal[j] and s[j] == goal[i]

Code Explanation

We first reject strings with different lengths:

if len(s) != len(goal):
    return False

A swap can rearrange characters, but it cannot add or remove characters.

Then we handle the equal-string case:

if s == goal:
    return len(set(s)) < len(s)

If the set has fewer elements than the string length, some character appears more than once. That means we can swap two equal characters and keep the same string.

Next, we collect mismatched positions:

diff = []

for i in range(len(s)):
    if s[i] != goal[i]:
        diff.append(i)

A valid one-swap transformation must have exactly two mismatches:

if len(diff) != 2:
    return False

Finally, we check whether swapping those two positions fixes both mismatches:

i, j = diff

return s[i] == goal[j] and s[j] == goal[i]

Testing

def test_buddy_strings():
    s = Solution()

    assert s.buddyStrings("ab", "ba") is True
    assert s.buddyStrings("ab", "ab") is False
    assert s.buddyStrings("aa", "aa") is True
    assert s.buddyStrings("aaaaaaabc", "aaaaaaacb") is True
    assert s.buddyStrings("", "aa") is False
    assert s.buddyStrings("abcd", "badc") is False
    assert s.buddyStrings("abcaa", "abcbb") is False

    print("all tests passed")

test_buddy_strings()

Test meaning: