LeetCode 859 - Buddy Strings
The problem asks whether it is possible to make two strings equal by performing exactly one swap operation on the first string s. A swap operation means choosing two different indices i and j in s and exchanging the characters at those positions.
Difficulty: 🟢 Easy
Topics: Hash Table, String
Solution
Problem Understanding
The problem asks whether it is possible to make two strings equal by performing exactly one swap operation on the first string s.
A swap operation means choosing two different indices i and j in s and exchanging the characters at those positions. After performing that single swap, the resulting string must match goal.
The input consists of two lowercase strings:
s, the string we are allowed to modifygoal, the target string we want to obtain
The output is a boolean:
trueif exactly one valid swap inscan make it equal togoalfalseotherwise
A very important detail is that the swap must involve two different indices. Swapping a character with itself is not allowed.
The constraints tell us that the string lengths can be as large as 2 * 10^4, so the solution must be efficient. A quadratic or cubic brute force approach could become too slow. Since the strings contain only lowercase English letters, we can take advantage of the small alphabet size when needed.
There are several important edge cases:
If the lengths of the strings differ, the answer is immediately false because no swap can change the length of a string.
If the strings are already equal, the answer is not automatically true. Since we must still perform a swap between two different indices, the string can remain unchanged only if there is at least one repeated character. For example:
"aa"can swap the two'a'characters and remain"aa""ab"becomes"ba"after swapping, so it cannot stay"ab"
Another important case occurs when the strings differ in more than two positions. One swap can fix at most two mismatched positions, so any larger mismatch count immediately makes the answer false.
Approaches
Brute Force Approach
The brute force idea is to try every possible pair of indices in s, perform the swap, and check whether the resulting string equals goal.
For a string of length n, there are approximately n^2 possible swaps. For each swap, constructing the new string and comparing it with goal takes O(n) time.
This guarantees correctness because every possible legal swap is tested. If any swap produces goal, we return true.
However, the total complexity becomes O(n^3) in the worst case:
O(n^2)swapsO(n)work per swap
With n up to 20,000, this is far too slow.
Optimal Approach
The key observation is that a single swap only affects two positions.
That means:
- If
sandgoaldiffer in more than two positions, one swap cannot fix them. - If they differ in exactly two positions, those mismatches must perfectly cross-match.
- If they differ in zero positions, we need at least one duplicate character so a swap can occur without changing the string.
Instead of trying all swaps, we only need to examine the mismatch positions between the two strings.
This reduces the problem to a single linear scan.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n³) | O(n) | Tries every possible swap and rebuilds strings |
| Optimal | O(n) | O(1) | Tracks mismatched positions and duplicate characters |
Algorithm Walkthrough
- First, check whether the lengths of
sandgoalare different. If they are, returnfalseimmediately because swapping characters cannot change string length. - Compare the two strings character by character and record all positions where they differ. Store these mismatches in a list.
- If there are more than two mismatches, return
false. One swap can only correct two positions. - If there are exactly two mismatches, suppose the mismatched pairs are:
(s[i], goal[i])(s[j], goal[j])
A single swap works only if:
s[i] == goal[j]s[j] == goal[i]
This means the mismatches cross-match perfectly after swapping. 5. If there are zero mismatches, the strings are already equal. In this case, we must determine whether a swap can leave the string unchanged.
This is possible only if some character appears at least twice. We can detect this by checking whether any character repeats in s.
6. If none of the above conditions succeed, return false.
Why it works
A swap only exchanges two characters, so it can only modify two positions in the string. Therefore:
- More than two mismatches can never be fixed.
- Exactly two mismatches are fixable only if swapping those two characters resolves both positions simultaneously.
- Zero mismatches require duplicate characters because the swap must still occur between distinct indices.
These conditions completely characterize all valid solutions.
Python Solution
class Solution:
def buddyStrings(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
mismatches = []
for i in range(len(s)):
if s[i] != goal[i]:
mismatches.append(i)
if len(mismatches) == 2:
i, j = mismatches
return s[i] == goal[j] and s[j] == goal[i]
if len(mismatches) == 0:
seen = set()
for ch in s:
if ch in seen:
return True
seen.add(ch)
return False
The implementation begins with a length check because unequal lengths make the transformation impossible.
Next, the code scans both strings simultaneously and records every index where the characters differ. This mismatch list is the central piece of information for the algorithm.
If exactly two mismatches exist, the code verifies the cross-match condition. Swapping the characters at those two positions in s should produce the corresponding characters in goal.
If there are no mismatches, the strings are already equal. The code then checks for duplicate characters using a set. If a duplicate exists, swapping the two identical characters leaves the string unchanged, which satisfies the problem requirement.
Finally, all other situations return False.
Go Solution
func buddyStrings(s string, goal string) bool {
if len(s) != len(goal) {
return false
}
mismatches := []int{}
for i := 0; i < len(s); i++ {
if s[i] != goal[i] {
mismatches = append(mismatches, i)
}
}
if len(mismatches) == 2 {
i := mismatches[0]
j := mismatches[1]
return s[i] == goal[j] && s[j] == goal[i]
}
if len(mismatches) == 0 {
seen := make(map[byte]bool)
for i := 0; i < len(s); i++ {
if seen[s[i]] {
return true
}
seen[s[i]] = true
}
}
return false
}
The Go implementation follows the same logic as the Python version.
One small difference is the use of map[byte]bool instead of a Python set for duplicate detection. Since the input contains only lowercase English letters, using bytes is efficient and straightforward.
Go strings are byte-indexed, so accessing characters with s[i] works correctly for lowercase ASCII input.
Worked Examples
Example 1
Input:
s = "ab"
goal = "ba"
We compare characters position by position.
| Index | s[i] | goal[i] | Match? |
|---|---|---|---|
| 0 | a | b | No |
| 1 | b | a | No |
Mismatch indices:
[0, 1]
Now check cross-match condition:
| Check | Result |
|---|---|
| s[0] == goal[1] | a == a |
| s[1] == goal[0] | b == b |
Both conditions are true, so return true.
Example 2
Input:
s = "ab"
goal = "ab"
Character comparison:
| Index | s[i] | goal[i] | Match? |
|---|---|---|---|
| 0 | a | a | Yes |
| 1 | b | b | Yes |
Mismatch list:
[]
Since the strings are already equal, we check for duplicates.
| Character | Seen Before? |
|---|---|
| a | No |
| b | No |
No duplicate characters exist, so any swap changes the string.
Return false.
Example 3
Input:
s = "aa"
goal = "aa"
Character comparison:
| Index | s[i] | goal[i] | Match? |
|---|---|---|---|
| 0 | a | a | Yes |
| 1 | a | a | Yes |
Mismatch list:
[]
Now check duplicates.
| Character | Seen Before? |
|---|---|
| a | No |
| a | Yes |
A duplicate exists, so swapping the two 'a' characters leaves the string unchanged.
Return true.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Single pass through the strings |
| Space | O(1) | At most a few mismatch indices and 26 characters stored |
The algorithm scans the strings once to identify mismatches, which takes linear time.
The auxiliary space is constant because the mismatch list can contain at most a few indices relevant to the decision, and the duplicate check uses at most 26 lowercase letters.
Test Cases
solution = Solution()
assert solution.buddyStrings("ab", "ba") == True # basic valid swap
assert solution.buddyStrings("ab", "ab") == False # equal strings without duplicates
assert solution.buddyStrings("aa", "aa") == True # equal strings with duplicates
assert solution.buddyStrings("abcd", "badc") == False # more than two mismatches
assert solution.buddyStrings("abcd", "abdc") == True # exactly one valid swap
assert solution.buddyStrings("abcd", "abcd") == False # equal string without repeated chars
assert solution.buddyStrings("aaaaaaabc", "aaaaaaacb") == True # swap near end
assert solution.buddyStrings("abcaa", "abcbb") == False # mismatches do not cross-match
assert solution.buddyStrings("a", "a") == False # single char cannot swap
assert solution.buddyStrings("ab", "ca") == False # invalid mismatch structure
assert solution.buddyStrings("abab", "abab") == True # equal string with duplicates
assert solution.buddyStrings("abc", "bac") == True # swap first two chars
assert solution.buddyStrings("abc", "def") == False # completely different strings
assert solution.buddyStrings("abcd", "abcf") == False # one mismatch only
assert solution.buddyStrings("", "") == False if False else True # placeholder for non-empty constraint
| Test | Why |
|---|---|
"ab", "ba" |
Basic successful swap |
"ab", "ab" |
Equal strings without duplicates |
"aa", "aa" |
Equal strings with duplicate characters |
"abcd", "badc" |
More than two mismatches |
"abcd", "abdc" |
Valid swap in middle positions |
"abcd", "abcd" |
Already equal but no repeated character |
"aaaaaaabc", "aaaaaaacb" |
Large repeated prefix |
"abcaa", "abcbb" |
Two mismatches that do not cross-match |
"a", "a" |
Minimum length edge case |
"ab", "ca" |
Impossible transformation |
"abab", "abab" |
Equal strings with multiple duplicates |
"abc", "bac" |
Swap involving first characters |
"abc", "def" |
Entirely different strings |
"abcd", "abcf" |
Single mismatch cannot be fixed |
Edge Cases
One important edge case occurs when the strings are already equal. Many incorrect implementations immediately return true in this situation. However, the problem requires a swap between two distinct indices. If every character is unique, any swap changes the string. The implementation correctly handles this by checking for duplicate characters before returning true.
Another tricky case is when the strings differ in only one position. A single swap always changes two positions simultaneously, so one mismatch can never be fixed. The algorithm naturally handles this because it only accepts exactly zero or exactly two mismatches.
A third important edge case is when the strings differ in more than two positions. Some naive solutions may attempt multiple fixes mentally, but only one swap is allowed. Since swapping affects exactly two indices, more than two mismatches make the transformation impossible. The implementation immediately rejects such inputs.
A subtle case involves two mismatches that do not cross-match correctly. For example:
s = "ab"
goal = "cd"
There are two mismatches, but swapping 'a' and 'b' cannot create 'c' and 'd'. The implementation verifies the exact cross-match condition to ensure correctness.
Finally, single-character strings require special attention. Since a swap requires two distinct indices, a string of length one can never perform a valid swap. The implementation handles this naturally because there can be no duplicate characters and no valid pair of mismatch indices.