# Check if One String Swap Can Make Strings Equal
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-one-string-swap-can-make-strings-equal)
Canonical: https://scaleengineer.com/dsa/problems/check-if-one-string-swap-can-make-strings-equal
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## Problem
You are given two strings `s1` and `s2` of equal length. A **string swap** is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return `true` _if it is possible to make both strings equal by performing **at most one string swap** on **exactly one** of the strings._ Otherwise, return `false`.

**Example 1:**

**Input:** s1 = "bank", s2 = "kanb"
**Output:** true
**Explanation:** For example, swap the first character with the last character of s2 to make "bank".

**Example 2:**

**Input:** s1 = "attack", s2 = "defend"
**Output:** false
**Explanation:** It is impossible to make them equal with one string swap.

**Example 3:**

**Input:** s1 = "kelb", s2 = "kelb"
**Output:** true
**Explanation:** The two strings are already equal, so no string swap operation is required.

**Constraints:**

* `1 <= s1.length, s2.length <= 100`
* `s1.length == s2.length`
* `s1` and `s2` consist of only lowercase English letters.

# Approaches
## Brute Force by Generating All Swaps
This approach systematically tries every possible single swap on one of the strings (`s1`) and checks if the result equals the other string (`s2`). It also handles the case where the strings are already equal, which requires zero swaps.
**Time:** O(N^3). The nested loops run in `O(N^2)` time. Inside the inner loop, `s1.toCharArray()` takes `O(N)`, creating a `new String()` takes `O(N)`, and `equals()` takes `O(N)`. This leads to a total time complexity of `O(N^2 * N) = O(N^3)`. · **Space:** O(N). We use a character array of size `N` to perform the swap inside the loops.
**Pros:** Simple and straightforward to understand.; Directly models the problem statement by trying all possible swaps.
**Cons:** Highly inefficient due to the cubic time complexity.; For larger strings (though not an issue with the given constraints), this would be too slow.; It performs many redundant operations.
### Explanation
The core idea is to explore all outcomes of performing exactly one swap on `s1`.

1.  **Check for equality**: First, we handle the base case. If `s1` and `s2` are already identical, no swap is needed. The condition "at most one swap" is satisfied, so we return `true`.
2.  **Generate all swaps**: If they are not equal, we proceed to try one swap. We can use nested loops to pick two distinct indices, `i` and `j`, from `s1`.
3.  **Swap and Compare**: For each pair of indices `(i, j)`, we create a new string by swapping the characters `s1[i]` and `s1[j]`. We then compare this newly formed string with `s2`. If they are equal, we have found a valid single swap, and we can return `true`.
4.  **Return false**: If we iterate through all possible pairs of indices and none of the resulting swaps make `s1` equal to `s2`, it means it's impossible to do so with a single swap. In this case, we return `false`.

```java
class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                char[] s1Chars = s1.toCharArray();
                char temp = s1Chars[i];
                s1Chars[i] = s1Chars[j];
                s1Chars[j] = temp;
                String swappedS1 = new String(s1Chars);
                if (swappedS1.equals(s2)) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- First, handle the base case: if `s1` and `s2` are already identical, no swap is needed. The condition "at most one swap" is satisfied, so we return `true`.
- If they are not equal, we proceed to try one swap. We can use nested loops to pick two distinct indices, `i` and `j`, from `s1`.
- For each pair of indices `(i, j)`, we create a new string by swapping the characters `s1[i]` and `s1[j]`.
- We then compare this newly formed string with `s2`. If they are equal, we have found a valid single swap, and we can return `true`.
- If we iterate through all possible pairs of indices and none of the resulting swaps make `s1` equal to `s2`, it means it's impossible to do so with a single swap. In this case, we return `false`.

## Single Pass to Find Differences
This is a highly efficient approach that solves the problem in a single pass through the strings. Instead of generating swaps, it analyzes the differences between `s1` and `s2`. The logic is based on the observation that for one swap to make the strings equal, there can be at most two positions where the strings differ.
**Time:** O(N). We iterate through the strings once to find the differences. The subsequent checks on the number of differences take constant time. · **Space:** O(1). The list of differences will store at most a constant number of indices (2) for the condition to be potentially true. If the list grows larger, we will eventually return false. Thus, the space is bounded by a small constant.
**Pros:** Optimal time complexity.; Solves the problem with a single pass.; Minimal space usage.
**Cons:** The logic is slightly more complex than the brute-force approach, as it requires reasoning about the number of differences.
### Explanation
We can determine if one swap is sufficient by counting the number of positions where `s1` and `s2` have different characters.

We iterate from the beginning to the end of the strings, comparing characters at each index `i`. We use a list to store the indices where `s1[i] != s2[i]`. During the iteration, if we find more than two differing positions, we can immediately conclude that more than one swap would be required. Thus, we can stop and return `false`.

After iterating through the entire strings, we analyze the list of differing indices:

- **Case 1: The list is empty.** This means `s1` and `s2` are identical. No swap is needed, so we return `true`.
- **Case 2: The list contains exactly two indices, say `i` and `j`.** This means the strings differ at precisely two locations. A single swap can make them equal only if swapping the characters in `s1` at these two positions results in `s2`. This means `s1[i]` must be equal to `s2[j]`, and `s1[j]` must be equal to `s2[i]`. If this condition holds, we return `true`; otherwise, `false`.
- **Case 3: The list contains any other number of indices (e.g., one, three, or more).** It's impossible to make the strings equal with a single swap. If there's one difference, a swap would affect two positions, making things worse. If there are more than two differences, a single swap can only fix at most two of them. So, in these cases, we return `false`.

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

class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff.add(i);
            }
        }

        if (diff.isEmpty()) {
            // Case 1: Strings are already equal
            return true;
        }

        if (diff.size() == 2) {
            // Case 2: Exactly two differences
            int i = diff.get(0);
            int j = diff.get(1);
            return s1.charAt(i) == s2.charAt(j) && s1.charAt(j) == s2.charAt(i);
        }

        // Case 3: 1 or >2 differences, impossible to fix with one swap
        return false;
    }
}
```
### Algorithm
- Initialize an empty list, `diff_indices`, to store the indices where characters mismatch.
- Iterate from `i = 0` to `n-1` (where `n` is the length of the strings).
- At each index `i`, compare `s1.charAt(i)` and `s2.charAt(i)`.
- If they are different, add the index `i` to `diff_indices`.
- If at any point the size of `diff_indices` becomes greater than 2, we can immediately return `false`.
- After the loop, check the size of `diff_indices`:
  - If the size is 0, it means the strings are already equal. Return `true`.
  - If the size is 2, let the indices be `i = diff_indices.get(0)` and `j = diff_indices.get(1)`. Check if `s1.charAt(i) == s2.charAt(j)` AND `s1.charAt(j) == s2.charAt(i)`. If both are true, return `true`. Otherwise, return `false`.
  - If the size is anything else (e.g., 1), return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean areAlmostEqual(String s1, String s2) {
    int cnt = 0;
    char c1 = 0, c2 = 0;
    for (int i = 0; i < s1.length(); ++i) {
      char a = s1.charAt(i), b = s2.charAt(i);
      if (a != b) {
        if (++cnt > 2 || (cnt == 2 && (a != c2 || b != c1))) {
          return false;
        }
        c1 = a;
        c2 = b;
      }
    }
    return cnt != 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool areAlmostEqual(string s1, string s2) {
    int cnt = 0;
    char c1 = 0, c2 = 0;
    for (int i = 0; i < s1.size(); ++i) {
      char a = s1[i], b = s2[i];
      if (a != b) {
        if (++cnt > 2 || (cnt == 2 && (a != c2 || b != c1))) {
          return false;
        }
        c1 = a, c2 = b;
      }
    }
    return cnt != 1;
  }
};

```

### Python

```python
class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool: cnt = 0 c1 = c2 = None for a, b in zip(s1, s2): if a != b: cnt += 1 if cnt > 2 or (cnt == 2 and (a != c2 or b != c1)): return False c1, c2 = a, b return cnt != 1

```