Buddy Strings: One Swap to Make Strings Equal

Can you make two strings equal by swapping exactly one pair of characters in the first string? That is LeetCode 859: Buddy Strings, rated easy. The trick is that "exactly one swap" introduces a subtle special case that catches a lot of people off guard.

The problem

Given two strings s and goal, return True if you can swap two characters in s so that the result equals goal. You must swap exactly once, and you swap two positions in s (not one from each string).

Input:  s = "ab", goal = "ba"
Output: True  # swap s[0] and s[1]

Input:  s = "ab", goal = "ab"
Output: False  # strings are already equal, but no valid swap exists (all characters are unique)

Input:  s = "aa", goal = "aa"
Output: True  # swap s[0] and s[1], string stays the same

Input:  s = "abcd", goal = "acbd"
Output: True  # swap s[1] and s[2]

Breaking it down

There are two main cases to consider:

Case 1: s and goal differ at some positions. For a single swap to fix things, there must be exactly two positions where they differ. And the characters at those two positions must cross-match: s[i] == goal[j] and s[j] == goal[i].

Case 2: s and goal are already identical. You still need to perform a swap, so you need two positions with the same character. In other words, s must contain at least one duplicate character. Swapping two identical characters leaves the string unchanged, which satisfies the requirement.

If neither case applies, the answer is False.

The key insight

The core logic boils down to two checks:

1. Find all indices where s[i] != goal[i]. Call this list diffs.
2. If len(diffs) == 2: check that s[diffs[0]] == goal[diffs[1]] and s[diffs[1]] == goal[diffs[0]].
3. If len(diffs) == 0: check that s has at least one duplicate character (use a set or frequency count).
4. Any other number of differences means no single swap can work.

That is the entire algorithm. No sorting, no complex data structures. Just one pass to collect differences and one check at the end.

Step-by-step walkthrough

Let's trace through s = "abcd" and goal = "acbd".

The algorithm walks through both strings once, collects the two differing positions, confirms the cross-match, and returns True.

The code

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

    if s == goal:
        # Need at least one duplicate character to swap
        return len(set(s)) < len(s)

    # Collect positions where s and goal differ
    diffs = []
    for i in range(len(s)):
        if s[i] != goal[i]:
            diffs.append(i)

    # Must have exactly 2 differences that cross-match
    if len(diffs) != 2:
        return False

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

Let's break down each part:

• Length check. If s and goal have different lengths, no single swap (or any number of swaps) can make them equal. Return False immediately.
• Equal strings check. If the strings are already the same, you need a "free" swap. That is only possible when s has duplicate characters. len(set(s)) < len(s) checks this in O(n) time.
• Collect differences. Walk through both strings and record every index where they differ.
• Exactly 2 differences. If there are fewer than 2 or more than 2 differences, a single swap cannot fix it. With exactly 2, check that swapping those two positions in s would produce goal.

Complexity analysis

Time: One pass through both strings to collect differences. The set construction for the equal-strings case is also O(n). Total: O(n) where n is the length of the strings.

Space: The diffs list holds at most 2 entries (you can short-circuit after 3). The set holds at most 26 characters for lowercase English letters. Both are bounded by constants, so the space is O(1).

The building blocks

Pairwise comparison with difference collection

The pattern of walking two sequences in parallel and collecting positions where they differ is reusable. You see it in edit distance variations, string matching, and anywhere you need to quantify how two sequences differ.

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

Duplicate detection with a set

Checking len(set(s)) < len(s) is a one-liner for "does this string have any repeated characters?" The set discards duplicates, so if its size is smaller than the original, at least one character appeared more than once. This same trick works for arrays, lists, or any iterable.

has_duplicate = len(set(s)) < len(s)

Edge cases

• Different lengths. s = "ab", goal = "abc". Return False immediately. No swap can change the length of a string.
• No differences (with duplicates). s = "aab", goal = "aab". The strings are equal and s has a duplicate a. You can swap the two a values and the string stays the same. Return True.
• No differences (no duplicates). s = "abc", goal = "abc". The strings are equal but every character is unique. Any swap would change s, so it could not equal goal after the swap. Return False.
• More than 2 differences. s = "abcd", goal = "dcba". Four positions differ. No single swap can fix all of them. Return False.
• Exactly 1 difference. s = "abc", goal = "adc". Only one position differs. A swap always changes two positions, so one difference is impossible to fix with a swap. Return False.
• Cross-match fails. s = "ab", goal = "cd". Two differences, but s[0] != goal[1]. The swap would not produce the right characters. Return False.

From understanding to recall

This problem is deceptively simple. The main logic is a single loop and a couple of checks. But the edge case where s == goal is the one that trips people up. If you remember "two cases: different strings need exactly 2 cross-matching diffs, equal strings need a duplicate," the whole solution follows naturally.

Practice by writing the solution from scratch with s = "ab", goal = "ba" and then s = "aa", goal = "aa". Make sure you handle both paths. After a few repetitions, the length check, the equal-strings branch, and the difference-collection loop will feel automatic.

Related posts

• Valid Anagram - Another string comparison problem using character frequency counting
• Isomorphic Strings - Checking structural equivalence between two strings with mapping
• Word Pattern - Pattern matching between a string and a sequence of words