Buddy Strings

Problem

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".

Constraints

• 1 <= s.length, goal.length <= 2 * 104
• s and goal consist of lowercase letters.

Solution

The problem Buddy Strings can be solved by considering 3 cases. First, when the lengths of s and goal are different, no matter which letters are swapped in s, the result would never be equal to goal. Next, if s and goal is identical, then swapping 2 letters in s can result in goal only if there exists a character in s which appears at least twice. Finally, when s and goal are different, then we can test swapping 2 characters from s that are different from goal and check if the result matches goal.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool buddyStrings(string s, string goal)
    {
        if (s.length() != goal.length())
            return false;

        unordered_set<char> hashset;
        if (s == goal)
        {
            for (char &ch : s)
            {
                if (hashset.find(ch) != hashset.end())
                    return true;
                hashset.insert(ch);
            }
            return false;
        }

        int idx = -1;
        for (int i = 0; i < s.length(); i++)
            if (s[i] != goal[i])
            {
                if (idx == -1)
                    idx = i;
                else
                {
                    swap(s[idx], s[i]);
                    break;
                }
            }

        return s == goal;
    }
};