Buddy Strings | GOOGLE | META | Leetcode-859 | Explanation ➕ Live Coding
Buddy Strings - Video Solution
Watch 10 video solutions for Buddy Strings, a easy level problem involving Hash Table, String. This walkthrough by codestorywithMIK has 13,487 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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].
- For example, swapping at indices
0and2in"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 * 104sandgoalconsist of lowercase letters.
Approach Overview
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.
Complexity Analysis
| 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. |