Buddy Strings

Difficulty: Easy | Acceptance: 34.00% | Paid: No Topics: Hash Table, String

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 0 and 2 in “abcd” results in “cbad”.

• Examples
• Constraints
• Brute Force Simulation
• Optimal Counting and Comparison

Examples

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 indices 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 * 10⁴
s and goal consist of lowercase letters.

Brute Force Simulation

Intuition Try swapping every possible pair of indices in the string s and check if the resulting string matches goal.

Steps

• If the lengths of s and goal are different, return false immediately.
• Convert s into a list of characters to allow easy swapping.
• Iterate through all pairs of indices (i, j) where i < j.
• Swap the characters at i and j.
• Check if the modified list equals goal.
• If it matches, return true.
• Swap the characters back to restore the original string for the next iteration.
• If the loop finishes without finding a match, return false.

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        
        s_list = list(s)
        n = len(s_list)
        
        for i in range(n):
            for j in range(i + 1, n):
                # Swap
                s_list[i], s_list[j] = s_list[j], s_list[i]
                
                if "".join(s_list) == goal:
                    return True
                
                # Swap back
                s_list[i], s_list[j] = s_list[j], s_list[i]
                
        return False

Complexity

• Time: O(n²) where n is the length of the string. We iterate through all pairs.
• Space: O(n) to store the character array/list.
• Notes: This approach is simple but will result in Time Limit Exceeded (TLE) for large inputs (n = 2 * 10⁴).

Optimal Counting and Comparison

Intuition We only need to check specific conditions based on the relationship between s and goal. If they are identical, we need a duplicate character to swap. If they differ, there must be exactly two mismatched positions, and the characters at those positions must be cross-equal.

Steps

• If the lengths of s and goal are different, return false.
• If s is equal to goal:
  • Check if there is any character that appears at least twice in s (using a frequency array or set).
  • If a duplicate exists, return true (swapping the duplicates results in the same string).
  • Otherwise, return false.
• If s is not equal to goal:
  • Iterate through the strings and collect the indices where characters differ.
  • If the number of differing indices is not exactly 2, return false.
  • Check if s[index1] == goal[index2] and s[index2] == goal[index1].
  • If true, return true; otherwise, return false.

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        
        if s == goal:
            # Check if there is a duplicate character to swap
            seen = set()
            for char in s:
                if char in seen:
                    return True
                seen.add(char)
            return False
        else:
            # Find indices where characters differ
            diffs = []
            for i in range(len(s)):
                if s[i] != goal[i]:
                    diffs.append(i)
                    if len(diffs) > 2:
                        return False
            
            # Must be exactly 2 differences and cross-match
            return len(diffs) == 2 and s[diffs[0]] == goal[diffs[1]] and s[diffs[1]] == goal[diffs[0]]

Complexity

• Time: O(n) where n is the length of the string. We traverse the string at most twice.
• Space: O(1) if using a fixed-size frequency array (26 letters), or O(n) in the worst case for the set approach if all characters are unique (though the alphabet is limited).
• Notes: This is the optimal solution for this problem.