Buddy Strings

Problem Statement

In this problem, we are provided with two strings s and goal. The task is to determine whether we can make the string s equal to goal by performing a single swap of two letters within s. A swap involves choosing two different indices i and j in string s, and exchanging the characters at these positions. The function should return true if such a swap can transform s into goal, and false otherwise. For example, in the string "abcd", swapping the characters at indices 0 and 2 results in the string "cbad". This problem tests our ability to manipulate strings and understand conditions under which character positions in strings can be swapped to match a target string configuration.

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 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 * 104
• s and goal consist of lowercase letters.

Approach and Intuition

Based on the provided examples and constraints, the problem can be approached systematically:

1. Initial Check of String Lengths:
   If the lengths of s and goal differ, a swap within s cannot equate it to goal. Hence, return false immediately.

2. Checking if s and goal are Already Equal:

   • If s is equal to goal, then we specifically check for the presence of any duplicate characters in s. This is because we can swap these duplicates to give the same string.
   • If there are no duplicate characters, and s is equal to goal, return false, as swapping non-duplicate characters would just mess up the alignment without changing the string.

3. Identifying Characters to Swap:

   • Traverse through the strings s and goal. Maintain a count of the positions where the characters in s do not match those in goal.
   • If at the end of the traversal, exactly two positions are mismatched, proceed to the next check. Otherwise, return false.

4. Validating the Possible Swap:

   • Given the two mismatched positions, check if swapping these characters in s leads to a string that matches goal. Specifically, if s[i] matches goal[j] and s[j] matches goal[i] where i and j are the mismatched positions, the swap is valid and return true.
   • If not, return false.

This approach efficiently checks whether two mismatched indices can be swapped to transform s into goal, focusing on alignment and character equality post-swap. The condition checks and string traversals ensure we do not perform any unnecessary operations, adhering closely to the problem's constraints.

Solutions

class Solution {
public:
    bool buddyStrings(string str1, string str2) {
        if (str1.size() != str2.size()) {
            return false;
        }
    
        if (str1 == str2) {
            vector<int> freq(26, 0);
            for (char c : str1) {
                freq[c - 'a']++;
                if (freq[c - 'a'] > 1) {
                    return true;
                }
            }
            return false;
        }
            
        int first_diff = -1;
        int second_diff = -1;
    
        for (int idx = 0; idx < str1.size(); ++idx) {
            if (str1[idx] != str2[idx]) {
                if (first_diff == -1) {
                    first_diff = idx;
                } else if (second_diff == -1) {
                    second_diff = idx;
                } else {
                    return false;
                }
            }
        }
    
        if (second_diff == -1) {
            return false;
        }
            
        return str1[first_diff] == str2[second_diff] && 
               str1[second_diff] == str2[first_diff];
    }
};