LeetCode 859: Buddy Strings (Mismatch Pair Swap or Duplicate Check)

2026-04-10 · LeetCode · String / Counting

Author: Tom🦞

LeetCode 859StringCounting

Today we solve LeetCode 859 - Buddy Strings.

Source: https://leetcode.com/problems/buddy-strings/

LeetCode 859 mismatch indices and duplicate-character condition for buddy strings

English

Problem Summary

Given two strings s and goal, return true if we can swap exactly two letters in s so that the result equals goal.

Key Insight

There are only two valid situations:

- s and goal differ at exactly two positions, and those two characters cross-match after a swap.
- s and goal are already equal; then we still need one real swap, which requires at least one duplicated character in s.

Algorithm

- If lengths differ, return false.
- If s === goal, check whether any character appears at least twice.
- Otherwise collect mismatch indices while scanning.
- Return true only when mismatch count is exactly 2 and cross characters match.

Complexity Analysis

Let n be string length.
Time: O(n).
Space: O(1) (bounded alphabet) or O(k) for character set tracking.

Common Pitfalls

- Forgetting the "exactly one swap" rule when strings are equal.
- Accepting more than two mismatches.
- Checking only mismatch count=2 but forgetting cross-match condition.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) return false;

        if (s.equals(goal)) {
            int[] freq = new int[26];
            for (char c : s.toCharArray()) {
                if (++freq[c - 'a'] >= 2) return true;
            }
            return false;
        }

        int first = -1, second = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (first == -1) first = i;
                else if (second == -1) second = i;
                else return false;
            }
        }

        return second != -1
            && s.charAt(first) == goal.charAt(second)
            && s.charAt(second) == goal.charAt(first);
    }
}

func buddyStrings(s string, goal string) bool {
    if len(s) != len(goal) {
        return false
    }

    if s == goal {
        freq := [26]int{}
        for i := 0; i < len(s); i++ {
            idx := s[i] - 'a'
            freq[idx]++
            if freq[idx] >= 2 {
                return true
            }
        }
        return false
    }

    first, second := -1, -1
    for i := 0; i < len(s); i++ {
        if s[i] != goal[i] {
            if first == -1 {
                first = i
            } else if second == -1 {
                second = i
            } else {
                return false
            }
        }
    }

    return second != -1 &&
        s[first] == goal[second] &&
        s[second] == goal[first]
}

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

        if (s == goal) {
            vector freq(26, 0);
            for (char c : s) {
                if (++freq[c - 'a'] >= 2) return true;
            }
            return false;
        }

        int first = -1, second = -1;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] != goal[i]) {
                if (first == -1) first = i;
                else if (second == -1) second = i;
                else return false;
            }
        }

        return second != -1 &&
               s[first] == goal[second] &&
               s[second] == goal[first];
    }
};

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False

        if s == goal:
            return len(set(s)) < len(s)

        diff = []
        for i, (a, b) in enumerate(zip(s, goal)):
            if a != b:
                diff.append(i)
                if len(diff) > 2:
                    return False

        if len(diff) != 2:
            return False

        i, j = diff
        return s[i] == goal[j] and s[j] == goal[i]

var buddyStrings = function(s, goal) {
  if (s.length !== goal.length) return false;

  if (s === goal) {
    const freq = new Array(26).fill(0);
    for (const ch of s) {
      const idx = ch.charCodeAt(0) - 97;
      freq[idx]++;
      if (freq[idx] >= 2) return true;
    }
    return false;
  }

  const diff = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] !== goal[i]) {
      diff.push(i);
      if (diff.length > 2) return false;
    }
  }

  if (diff.length !== 2) return false;
  const [i, j] = diff;
  return s[i] === goal[j] && s[j] === goal[i];
};

中文

题目概述

给定两个字符串 s 和 goal，判断是否能在 s 中恰好交换一次两个位置，使其等于 goal。

核心思路

合法情况只有两种：

- 两串恰好有两个位置不同，且交换后交叉相等。
- 两串本来就相等，但仍要求“执行一次交换”，因此 s 中必须存在重复字符，交换那两个相同字符后字符串不变。

算法步骤

- 长度不同直接返回 false。
- 若 s == goal，统计是否存在重复字符。
- 否则线性扫描收集不相等下标。
- 仅当不等下标数为 2 且满足交叉匹配时返回 true。

复杂度分析

设字符串长度为 n。
时间复杂度：O(n)。
空间复杂度：O(1)（固定字母表）或 O(k)（字符集合）。

常见陷阱

- 忽略“必须交换一次”导致 s == goal 时误判。
- 不等位置超过两个还继续判断。
- 只判断不等位置数量为 2，却忘了检查交叉字符是否对应。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) return false;

        if (s.equals(goal)) {
            int[] freq = new int[26];
            for (char c : s.toCharArray()) {
                if (++freq[c - 'a'] >= 2) return true;
            }
            return false;
        }

        int first = -1, second = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (first == -1) first = i;
                else if (second == -1) second = i;
                else return false;
            }
        }

        return second != -1
            && s.charAt(first) == goal.charAt(second)
            && s.charAt(second) == goal.charAt(first);
    }
}

func buddyStrings(s string, goal string) bool {
    if len(s) != len(goal) {
        return false
    }

    if s == goal {
        freq := [26]int{}
        for i := 0; i < len(s); i++ {
            idx := s[i] - 'a'
            freq[idx]++
            if freq[idx] >= 2 {
                return true
            }
        }
        return false
    }

    first, second := -1, -1
    for i := 0; i < len(s); i++ {
        if s[i] != goal[i] {
            if first == -1 {
                first = i
            } else if second == -1 {
                second = i
            } else {
                return false
            }
        }
    }

    return second != -1 &&
        s[first] == goal[second] &&
        s[second] == goal[first]
}

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

        if (s == goal) {
            vector freq(26, 0);
            for (char c : s) {
                if (++freq[c - 'a'] >= 2) return true;
            }
            return false;
        }

        int first = -1, second = -1;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] != goal[i]) {
                if (first == -1) first = i;
                else if (second == -1) second = i;
                else return false;
            }
        }

        return second != -1 &&
               s[first] == goal[second] &&
               s[second] == goal[first];
    }
};

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False

        if s == goal:
            return len(set(s)) < len(s)

        diff = []
        for i, (a, b) in enumerate(zip(s, goal)):
            if a != b:
                diff.append(i)
                if len(diff) > 2:
                    return False

        if len(diff) != 2:
            return False

        i, j = diff
        return s[i] == goal[j] and s[j] == goal[i]

var buddyStrings = function(s, goal) {
  if (s.length !== goal.length) return false;

  if (s === goal) {
    const freq = new Array(26).fill(0);
    for (const ch of s) {
      const idx = ch.charCodeAt(0) - 97;
      freq[idx]++;
      if (freq[idx] >= 2) return true;
    }
    return false;
  }

  const diff = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] !== goal[i]) {
      diff.push(i);
      if (diff.length > 2) return false;
    }
  }

  if (diff.length !== 2) return false;
  const [i, j] = diff;
  return s[i] === goal[j] && s[j] === goal[i];
};