Problem Description

Given two strings s1 and s2 of equal length, determine if you can make s1 equal to s2 by swapping exactly one pair of characters in s1.

• You can choose any two different indices in s1 and swap the characters at those positions.
• The swap must be performed at most once (you may also choose not to swap if s1 == s2 already).
• Return true if it's possible to make s1 equal to s2 with at most one swap, otherwise return false.
• Constraints: 1 <= s1.length, s2.length <= 100, s1.length == s2.length, s1 and s2 consist of lowercase English letters.

Thought Process

The naive approach would be to try every possible pair of indices in s1, swap them, and check if the result matches s2. However, this is inefficient, especially for long strings.

Let's reason about the problem:

• If s1 is already equal to s2, then no swaps are needed. But, we need to check if a swap is allowed (since the problem says "at most one swap", not "exactly one").
• Otherwise, identify the positions where s1 and s2 differ. If there are more than 2 differences, one swap can't fix all of them.
• If there are exactly 2 differences, swapping those two positions in s1 might make it equal to s2. We need to check that the characters at those positions are "crossed" between the two strings.
• If there is only 1 difference, or more than 2, it's impossible to fix with one swap.

Solution Approach

We can solve this problem in a few clear steps:

1. Check for Equal Strings: If s1 is already equal to s2, return true. (Swapping is optional.)
2. Find Differences: Iterate through both strings and record the indices where the characters differ.
3. Analyze Differences:
   • If there are exactly 2 indices where s1 and s2 differ, check if swapping these two characters in s1 makes the strings equal.
   • If there are 0 differences, return true (no swap needed).
   • If there are any other number of differences, return false (impossible with one swap).
4. Swap Check: For the two differing positions i and j, check that s1[i] == s2[j] and s1[j] == s2[i].

This approach is efficient because we only need to scan the strings once, and all operations are constant time after that.

Example Walkthrough

Let's consider the example: s1 = "bank", s2 = "kanb".

1. Compare each character:
   • Index 0: 'b' vs 'k' (different)
   • Index 1: 'a' vs 'a' (same)
   • Index 2: 'n' vs 'n' (same)
   • Index 3: 'k' vs 'b' (different)
   Differences at indices 0 and 3.
2. Check if swapping s1[0] and s1[3] makes s1 equal to s2:
   • After swap: s1 becomes "kanb", which is exactly s2.
3. Return true.

Another example: s1 = "attack", s2 = "defend".

• There are more than 2 differences, so it's impossible to make them equal with one swap. Return false.

Time and Space Complexity

• Brute-force approach: Try all pairs of indices (O(n²)), swap, and compare. This is inefficient for large strings.
• Optimized approach (above):
  • Time Complexity: O(n), where n is the length of the strings. We only need one pass to find the differences.
  • Space Complexity: O(1) extra space, since we only store up to 2 indices (the positions where the strings differ).

Summary

The key insight is that only two mismatches can be fixed with a single swap, and we can find those mismatches efficiently by a single scan. This approach is both simple and optimal, avoiding unnecessary swaps or brute-force checks. By focusing on the positions where the strings differ, we can quickly determine if a one-swap transformation is possible.

Code Implementation

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        diff = []
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                diff.append(i)
            if len(diff) > 2:
                return False
        if len(diff) != 2:
            return False
        i, j = diff
        return s1[i] == s2[j] and s1[j] == s2[i]
      

class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        if (s1 == s2) return true;
        vector<int> diff;
        for (int i = 0; i < s1.size(); ++i) {
            if (s1[i] != s2[i])
                diff.push_back(i);
            if (diff.size() > 2)
                return false;
        }
        if (diff.size() != 2)
            return false;
        int i = diff[0], j = diff[1];
        return s1[i] == s2[j] && s1[j] == s2[i];
    }
};
      

class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        if (s1.equals(s2)) return true;
        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.size() > 2)
                return false;
        }
        if (diff.size() != 2)
            return false;
        int i = diff.get(0), j = diff.get(1);
        return s1.charAt(i) == s2.charAt(j) && s1.charAt(j) == s2.charAt(i);
    }
}
      

var areAlmostEqual = function(s1, s2) {
    if (s1 === s2) return true;
    let diff = [];
    for (let i = 0; i < s1.length; i++) {
        if (s1[i] !== s2[i])
            diff.push(i);
        if (diff.length > 2)
            return false;
    }
    if (diff.length !== 2)
        return false;
    let [i, j] = diff;
    return s1[i] === s2[j] && s1[j] === s2[i];
};