Buddy Strings

easy string hash table

Problem

Given two strings s and goal, return true if you can swap two letters in s (at two distinct positions) so that the result equals goal, otherwise return false.

Inputs = "ab", goal = "ba"

Outputtrue

Swapping s[0] and s[1] gives "ba".

goal

def buddy_strings(s, goal):
    if len(s) != len(goal):
        return False
    if s == goal:
        return len(set(s)) < len(s)
    diff = [i for i in range(len(s)) if s[i] != goal[i]]
    return len(diff) == 2 and \
        s[diff[0]] == goal[diff[1]] and s[diff[1]] == goal[diff[0]]

function buddyStrings(s, goal) {
  if (s.length !== goal.length) return false;
  if (s === goal) return new Set(s).size < s.length;
  const diff = [];
  for (let i = 0; i < s.length; i++)
    if (s[i] !== goal[i]) diff.push(i);
  return diff.length === 2 &&
    s[diff[0]] === goal[diff[1]] && s[diff[1]] === goal[diff[0]];
}

boolean buddyStrings(String s, String goal) {
    if (s.length() != goal.length()) return false;
    if (s.equals(goal)) {
        Set<Character> uniq = new HashSet<>();
        for (char c : s.toCharArray()) uniq.add(c);
        return uniq.size() < s.length();
    }
    List<Integer> diff = new ArrayList<>();
    for (int i = 0; i < s.length(); i++)
        if (s.charAt(i) != goal.charAt(i)) diff.add(i);
    return diff.size() == 2 &&
        s.charAt(diff.get(0)) == goal.charAt(diff.get(1)) &&
        s.charAt(diff.get(1)) == goal.charAt(diff.get(0));
}

bool buddyStrings(string s, string goal) {
    if (s.size() != goal.size()) return false;
    if (s == goal) {
        set<char> uniq(s.begin(), s.end());
        return uniq.size() < s.size();
    }
    vector<int> diff;
    for (int i = 0; i < (int)s.size(); i++)
        if (s[i] != goal[i]) diff.push_back(i);
    return diff.size() == 2 &&
        s[diff[0]] == goal[diff[1]] && s[diff[1]] == goal[diff[0]];
}

Explanation

We get exactly one swap of two positions in s and want to know if that single swap can turn s into goal. Instead of trying all swaps, we reason about the positions where the two strings differ.

First, if the lengths differ, a swap cannot help, so the answer is false.

There are two cases. If s already equals goal, we still must perform a swap, so we need two equal letters we can swap with no visible effect. That is true exactly when some character repeats, i.e. len(set(s)) < len(s).

Otherwise we collect the indices where s and goal disagree into a list diff. A single swap can fix things only if there are exactly two mismatches, and those two are mirror images: s[diff[0]] == goal[diff[1]] and s[diff[1]] == goal[diff[0]].

Example: s = "ab", goal = "ba". They differ at indices 0 and 1, and s[0]='a' equals goal[1]='a', s[1]='b' equals goal[0]='b', so swapping works and the answer is true.

Time: O(n) Space: O(1)