Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.
Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].
0 and 2 in "abcd" results in "cbad".
Example 1:
Input: s = "ab", goal = "ba" Output: true Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.
Example 2:
Input: s = "ab", goal = "ab" Output: false Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.
Example 3:
Input: s = "aa", goal = "aa" Output: true Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.
Constraints:
1 <= s.length, goal.length <= 2 * 104s and goal consist of lowercase letters.Problem Overview: You get two strings s and goal. The task is to determine whether swapping exactly two characters in s can make it equal to goal. The swap must involve two different indices, and only one swap is allowed.
Approach 1: Direct Comparison with Character Swapping (O(n) time, O(1) space)
Scan both strings and record the indices where characters differ. If more than two mismatches appear, the swap cannot fix the strings. When exactly two mismatches exist, verify that swapping those characters in s would match goal (i.e., s[i] == goal[j] and s[j] == goal[i]). A special case appears when the strings are already identical. In that case, a valid swap requires at least one duplicate character so the string remains unchanged after swapping identical letters.
This approach relies on simple iteration and constant memory. You compare characters position by position and keep at most two mismatch indices. The duplicate-character check can be done using a small set or frequency array. Because the algorithm performs a single pass through the strings, the time complexity is O(n) with O(1) extra space.
Approach 2: Character Frequency and Permutation Check (O(n) time, O(1) space)
Another way to reason about the problem is through character frequency and permutation validation. First ensure both strings have identical character counts using a frequency map or fixed-size array for letters. If the frequencies differ, no swap can make the strings equal. Next, count the number of positions where the characters differ. A valid buddy swap exists when there are exactly two mismatches forming a reversible pair.
This approach emphasizes verifying that both strings are permutations of each other before analyzing mismatches. The frequency structure is typically implemented with a hash map or array, making it a natural application of hash table techniques combined with linear scans of a string. Like the first method, it runs in O(n) time and uses O(1) extra space because the alphabet size is fixed.
Recommended for interviews: The direct comparison method is usually the expected solution. Interviewers want to see that you detect mismatched indices and reason about the exact swap condition. Mentioning the identical-string edge case (requiring duplicate characters) shows strong attention to detail. The frequency-based method also works, but the mismatch comparison demonstrates clearer reasoning about the swap constraint.
This approach involves a straightforward comparison between the two strings. First, check if both strings are equal in length. If not, return false immediately. Next, identify the indices where the two strings differ. If there are exactly two such indices and swapping these characters in the first string can make it identical to the second, return true. Additionally, handle the edge case where both strings are already identical but contain at least one character that repeats, in which case a swap is possible and returns true.
The function first checks if the strings are of different lengths, returning false immediately. It then handles the case when both strings are identical by checking for repeated characters using a set, since a swap is impossible without repetition. For differing strings, it constructs a list of differing positions. If there are exactly two differences and swapping them resolves equality, the function returns true.
Python
JavaScript
Time Complexity: O(n), as we traverse the strings with a single pass to gather differences.
Space Complexity: O(1) for constant-space operations, though storing differences requires space proportional to the number of differences.
This alternative method relies on character frequency counts and permutation verifications. If the strings differ in length, they're immediately ruled out. By evaluating how character frequencies align and applying permutation checks, the function can discern valid swaps that potentially achieve the goal formation of the strings.
The Java Solution uses ArrayList to store differing indices while also handling special cases for direct equality and duplication presence. It'll iterate through the string, populating discrepancies only to check their viability for a simple swap.
Time Complexity: O(n), scanning all potential indices to locate and evaluate differences.
Space Complexity: O(n) theoretically with list storage though practically controlled by processing mechanism constraints.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direct Comparison with Character Swapping | Time Complexity: O(n), as we traverse the strings with a single pass to gather differences. |
| Character Frequency and Permutation Check | Time Complexity: O(n), scanning all potential indices to locate and evaluate differences. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Comparison with Character Swapping | O(n) | O(1) | Best general solution. Quickly identifies mismatched indices and verifies swap conditions. |
| Character Frequency and Permutation Check | O(n) | O(1) | Useful when reasoning through permutation equality and validating character counts before mismatch checks. |
Buddy Strings | GOOGLE | META | Leetcode-859 | Explanation ➕ Live Coding • codestorywithMIK • 12,534 views views
Watch 9 more video solutions →Practice Buddy Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor