Code Implementation

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        if s == goal:
            seen = set()
            for c in s:
                if c in seen:
                    return True
                seen.add(c)
            return False
        diffs = []
        for i in range(len(s)):
            if s[i] != goal[i]:
                diffs.append(i)
        if len(diffs) != 2:
            return False
        i, j = diffs
        return s[i] == goal[j] and s[j] == goal[i]
      

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if (s.length() != goal.length()) return false;
        if (s == goal) {
            vector<int> count(26, 0);
            for (char c : s) {
                count[c - 'a']++;
                if (count[c - 'a'] > 1) return true;
            }
            return false;
        }
        vector<int> diff;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] != goal[i]) diff.push_back(i);
        }
        if (diff.size() != 2) return false;
        return s[diff[0]] == goal[diff[1]] && s[diff[1]] == goal[diff[0]];
    }
};
      

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) return false;
        if (s.equals(goal)) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
                if (count[c - 'a'] > 1) return true;
            }
            return false;
        }
        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != goal.charAt(i)) diff.add(i);
        }
        if (diff.size() != 2) return false;
        int i = diff.get(0), j = diff.get(1);
        return s.charAt(i) == goal.charAt(j) && s.charAt(j) == goal.charAt(i);
    }
}
      

var buddyStrings = function(s, goal) {
    if (s.length !== goal.length) return false;
    if (s === goal) {
        let seen = new Set();
        for (let c of s) {
            if (seen.has(c)) return true;
            seen.add(c);
        }
        return false;
    }
    let diffs = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] !== goal[i]) diffs.push(i);
    }
    if (diffs.length !== 2) return false;
    let [i, j] = diffs;
    return s[i] === goal[j] && s[j] === goal[i];
};
      

Problem Description

You are given two strings, s and goal, of the same length. Your task is to determine if you can swap exactly two letters in s so that it becomes equal to goal. The swap must involve two different indices (i.e., you cannot swap a letter with itself at the same position), and you can perform at most one swap.

Key constraints:

• Both strings must have the same length.
• You can only swap two distinct indices in s at most once.
• If s is already equal to goal, you can only return true if there is at least one duplicate letter in s (so a swap can be made that leaves the string unchanged).

Thought Process

At first glance, the problem seems to require checking all possible pairs of swaps in s to see if any result in goal. However, this brute-force approach would be inefficient, especially for long strings.

Upon further consideration, we can optimize by observing:

• If s and goal are not the same length, it's impossible to make them equal.
• If s is already equal to goal, we need to check for duplicate characters. Only then can we swap two identical letters and still have the same string.
• If s and goal differ, we should look for exactly two positions where their characters differ. Swapping these two characters in s should make the strings equal.
• If the number of differing positions is anything other than two, it's impossible to achieve equality with a single swap.

Solution Approach

Let's break down the algorithm step by step:

1. Check Lengths: If s and goal are not the same length, return false immediately.
2. Check for Equality: If s is equal to goal:
   • Scan s for duplicate characters.
   • If any character appears more than once, return true (since swapping them keeps the string unchanged).
   • Otherwise, return false (since a swap would alter the string).
3. Find Differences: If s and goal are not equal:
   • Iterate through both strings and record the indices where the characters differ.
   • If there are exactly two differences, check if swapping these two characters in s would make the strings equal.
   • If so, return true; otherwise, return false.
   • If there are not exactly two differences, return false.

We use a set or an array to check for duplicate letters efficiently (O(n) time). We only need to store up to two indices where the characters differ, so space usage is minimal.

Example Walkthrough

Let's consider the example: s = "ab", goal = "ba".

1. Both strings have length 2, so we proceed.
2. s and goal are not equal, so we look for differences:
   • At index 0: s[0] = 'a', goal[0] = 'b' (different)
   • At index 1: s[1] = 'b', goal[1] = 'a' (different)
3. There are exactly two differences: indices 0 and 1.
4. Check if swapping s[0] and s[1] will result in goal:
   • Swap 'a' and 'b' in s to get "ba", which matches goal.
5. Return true.

Another example: s = "aa", goal = "aa".

• Strings are equal; check for duplicate letters.
• 'a' appears twice, so swapping them keeps the string unchanged.
• Return true.

If s = "ab", goal = "ab":

• No duplicate letters; swapping any two will change the string.
• Return false.

Time and Space Complexity

Brute-force Approach:

• Would require checking all O(n²) pairs of indices to swap and compare the resulting string each time.
• Time Complexity: O(n²)
• Space Complexity: O(n) for storing swapped strings.

• We scan both strings once to record differences and check for duplicates.
• Time Complexity: O(n), where n is the length of the strings.
• Space Complexity: O(1) (if using a fixed-size array for character counting; O(n) if using a set for all characters).

The optimized approach is much more efficient and suitable for large inputs.

Summary

To solve the Buddy Strings problem efficiently, we:

• First check if the strings are the same length.
• If they are equal, we look for duplicate letters to allow a swap that doesn't change the string.
• If not, we look for exactly two differing positions and check if swapping them makes the strings equal.