# LeetCode 859: Buddy Strings

## Problem Restatement

We are given two strings:

```python
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:

```python
s[i]
s[j]
```

If no such swap exists, return `False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `s`, the original string |
| Input | `goal`, the target string |
| Output | `True` if one swap can make `s == goal`, otherwise `False` |
| Constraint | The swap must use two different indices |

Function shape:

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

## Examples

Example 1:

```python
s = "ab"
goal = "ba"
```

Swap the two characters in `s`:

```python
"ab" -> "ba"
```

So the answer is:

```python
True
```

Example 2:

```python
s = "ab"
goal = "ab"
```

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

The only possible swap gives:

```python
"ab" -> "ba"
```

That does not equal `goal`, so the answer is:

```python
False
```

Example 3:

```python
s = "aa"
goal = "aa"
```

The strings are already equal.

We can swap the two equal characters:

```python
"aa" -> "aa"
```

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

So the answer is:

```python
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:

```python
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:

```python
s = "aa"
goal = "aa"
```

works, but:

```python
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:

```python
s[i] == goal[j]
s[j] == goal[i]
```

## Algorithm

First, check length:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the strings once |
| Space | `O(1)` | At most 26 lowercase letters are counted |

Here, `n` is the length of `s`.

## Implementation

```python
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:

```python
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:

```python
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:

```python
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:

```python
if len(diff) != 2:
    return False
```

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

```python
i, j = diff

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `"ab"` to `"ba"` | Basic valid swap |
| `"ab"` to `"ab"` | Equal strings without duplicate |
| `"aa"` to `"aa"` | Equal strings with duplicate |
| `"aaaaaaabc"` to `"aaaaaaacb"` | Valid swap near the end |
| `""` to `"aa"` | Different lengths |
| `"abcd"` to `"badc"` | More than one swap needed |
| `"abcaa"` to `"abcbb"` | Same mismatch count, wrong characters |