# Buddy Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/buddy-strings)
Canonical: https://scaleengineer.com/dsa/problems/buddy-strings
**Data structures:** Hash Table, String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## 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"`.

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

# Approaches
## Brute Force by Generating All Swaps
This approach involves generating every possible string that can be formed by swapping exactly two characters in `s` and checking if any of these generated strings match `goal`. It is a straightforward, exhaustive search method.
**Time:** O(N^3), where N is the length of the string. The nested loops give a factor of O(N^2). Inside the loop, converting the string to a `char[]` and then back to a `String` for comparison each take O(N) time, leading to an overall complexity of O(N^2 * N) = O(N^3). · **Space:** O(N), where N is the length of the string. A new character array of size N is created in each iteration of the inner loop.
**Pros:** Simple to understand and implement.; Correctly covers all cases without complex conditional logic.
**Cons:** Extremely inefficient for larger strings.; Will likely cause a 'Time Limit Exceeded' error on most coding platforms for the given constraints.
### Explanation
The brute-force method systematically tries every possible swap. It uses two nested loops to select two distinct indices, `i` and `j`, from the string `s`. For each pair of indices, it performs the swap on a temporary copy of the string (usually a character array for easy modification). After the swap, the modified array is converted back into a string and compared with the `goal` string. If a match is found, we've successfully found a way to make `s` equal to `goal` with one swap, and we can immediately return `true`.

This method implicitly handles all cases:
- If `s` and `goal` differ by a swap (e.g., `s="ab"`, `goal="ba"`), the loop will eventually find the correct `i` and `j` to make them equal.
- If `s` and `goal` are the same and `s` has duplicates (e.g., `s="aa"`, `goal="aa"`), swapping the duplicate characters will result in the same string, leading to a match.
- If `s` and `goal` are the same but `s` has no duplicates (e.g., `s="ab"`, `goal="ab"`), any swap will produce a different string, so no match will be found, and the function will correctly return `false` after checking all possibilities.

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

        // This handles both cases: s != goal and s == goal
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                char[] sChars = s.toCharArray();
                // Swap characters
                char temp = sChars[i];
                sChars[i] = sChars[j];
                sChars[j] = temp;
                
                if (String.valueOf(sChars).equals(goal)) {
                    return true;
                }
            }
        }

        return false;
    }
}
```
### Algorithm
- 1. First, check if the lengths of `s` and `goal` are different. If they are, return `false` as no swap can make them equal.
- 2. Use a nested loop to iterate through every unique pair of indices `(i, j)` in string `s`, where `i < j`.
- 3. For each pair, create a temporary copy of `s` as a character array.
- 4. Swap the characters at indices `i` and `j` in the temporary copy.
- 5. Convert the modified character array back to a string and compare it with `goal`.
- 6. If the new string is equal to `goal`, it means a single swap was sufficient. Return `true`.
- 7. If the loops complete without finding any such valid swap, it means it's impossible. Return `false`.

## Single Pass with Mismatch Tracking
This optimal approach solves the problem in a single pass by analyzing the properties of the strings. Instead of simulating swaps, it directly checks for the conditions that must be true for `s` and `goal` to be buddy strings. It efficiently handles the two main scenarios: when the strings are identical and when they are different.
**Time:** O(N), where N is the length of the strings. The `s.equals(goal)` check takes O(N). Both subsequent cases involve a single loop through the string, which is also O(N). Therefore, the total time complexity is linear. · **Space:** O(1). The `HashSet` will store at most 26 characters (the size of the alphabet), which is constant. The list of differences will only be processed if its size is 2, also constant. Thus, the space usage does not scale with the input size N.
**Pros:** Highly efficient with linear time complexity.; Optimal space complexity.; Passes for large inputs within time limits.
**Cons:** The logic is slightly more complex than the brute-force approach because it requires handling two separate cases.
### Explanation
This method is based on a logical analysis of the problem constraints. It avoids the costly process of generating and testing all possible swaps.

First, a basic check: if the strings don't have the same length, they can never be buddy strings, so we return `false`.

Next, we consider two distinct possibilities:

1.  **`s` and `goal` are the same string:** If `s.equals(goal)`, we can only return `true` if we can perform a swap on `s` that results in `s` itself. This is only possible if we swap two identical characters. Therefore, the problem reduces to checking if `s` has any duplicate characters. A `HashSet` is perfect for this: we iterate through `s`, adding characters to the set. If we try to add a character that's already in the set, we've found a duplicate, and we can return `true`.

2.  **`s` and `goal` are different strings:** For a single swap in `s` to produce `goal`, the two strings must differ in exactly two positions. We can find these positions by iterating through both strings simultaneously and recording the indices where `s.charAt(i) != goal.charAt(i)`. We store these indices in a list. If, after checking all characters, the number of differing indices is not exactly two, it's impossible to make them equal with one swap, so we return `false`. If there are exactly two differing indices, say `i` and `j`, we must perform one final check: the characters must be cross-matched. That is, `s[i]` must equal `goal[j]` and `s[j]` must equal `goal[i]`. If this holds, they are buddy strings; otherwise, they are not.

This approach covers all conditions in linear time.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

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

        if (s.equals(goal)) {
            Set<Character> distinctChars = new HashSet<>();
            for (char c : s.toCharArray()) {
                if (!distinctChars.add(c)) {
                    // Found a duplicate character, we can swap them to get the same string
                    return true;
                }
            }
            // No duplicates found, any swap will change the string
            return false;
        } else {
            List<Integer> diff = new ArrayList<>();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != goal.charAt(i)) {
                    diff.add(i);
                }
            }

            // If there are exactly two differing positions and the characters are swapped
            return (diff.size() == 2 &&
                    s.charAt(diff.get(0)) == goal.charAt(diff.get(1)) &&
                    s.charAt(diff.get(1)) == goal.charAt(diff.get(0)));
        }
    }
}
```
### Algorithm
- 1. First, check if the lengths of `s` and `goal` are not equal. If they aren't, return `false`.
- 2. **Case 1: `s` and `goal` are identical.**
  - If `s.equals(goal)`, a swap is only valid if we can swap two identical characters. 
  - To check this, iterate through `s` and use a `HashSet` or a frequency array to detect if there are any duplicate characters. 
  - If a duplicate character exists, return `true`. Otherwise, return `false`.
- 3. **Case 2: `s` and `goal` are different.**
  - Create a list to store the indices where the characters of `s` and `goal` do not match.
  - Iterate through the strings and add any mismatching index to the list.
  - After the iteration, if the list of differences does not contain exactly two indices, return `false`.
  - If the list contains exactly two indices, say `i` and `j`, check if the characters are swappable: `s.charAt(i) == goal.charAt(j)` and `s.charAt(j) == goal.charAt(i)`. 
  - If this condition is met, return `true`. Otherwise, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean buddyStrings(String s, String goal) {
    int m = s.length(), n = goal.length();
    if (m != n) {
      return false;
    }
    int diff = 0;
    int[] cnt1 = new int[26];
    int[] cnt2 = new int[26];
    for (int i = 0; i < n; ++i) {
      int a = s.charAt(i), b = goal.charAt(i);
      ++cnt1[a - 'a'];
      ++cnt2[b - 'a'];
      if (a != b) {
        ++diff;
      }
    }
    boolean f = false;
    for (int i = 0; i < 26; ++i) {
      if (cnt1[i] != cnt2[i]) {
        return false;
      }
      if (cnt1[i] > 1) {
        f = true;
      }
    }
    return diff == 2 || (diff == 0 && f);
  }
}

```

### Python

```python
class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool: m, n = len(s), len(goal) if m != n: return False cnt1, cnt2 = Counter(s), Counter(goal) if cnt1 != cnt2: return False diff = sum(s[i] != goal[i] for i in range(n)) return diff == 2 or (diff == 0 and any(v > 1 for v in cnt1 . values()))

```

### CPP

```cpp
class Solution {
public:
  bool buddyStrings(string s, string goal) {
    int m = s.size(), n = goal.size();
    if (m != n)
      return false;
    int diff = 0;
    vector<int> cnt1(26);
    vector<int> cnt2(26);
    for (int i = 0; i < n; ++i) {
      ++cnt1[s[i] - 'a'];
      ++cnt2[goal[i] - 'a'];
      if (s[i] != goal[i])
        ++diff;
    }
    bool f = false;
    for (int i = 0; i < 26; ++i) {
      if (cnt1[i] != cnt2[i])
        return false;
      if (cnt1[i] > 1)
        f = true;
    }
    return diff == 2 || (diff == 0 && f);
  }
};

```