Check if One String Swap Can Make Strings Equal

easy string counting

Problem

You are given two strings s1 and s2 of the same length, both made of lowercase letters. You may perform at most one swap: pick two indices in one of the strings (possibly the same index) and exchange the characters at those positions. Return true if the two strings can be made identical with at most one such swap, and false otherwise.

Inputs1 = "bank", s2 = "kanb"

Outputtrue

The strings differ at indices 0 and 3, and the pairs cross-match ('b'/'k' vs 'k'/'b'), so swapping s1[0] with s1[3] turns "bank" into "kanb".

s1 (lowercase letters)

s2 (same length as s1)

def are_almost_equal(s1, s2):
    diff = []
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            diff.append(i)
            if len(diff) > 2:
                return False
    if not diff:
        return True
    if len(diff) != 2:
        return False
    i, j = diff
    return s1[i] == s2[j] and s1[j] == s2[i]

function areAlmostEqual(s1, s2) {
  const 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 === 0) return true;
  if (diff.length !== 2) return false;
  const [i, j] = diff;
  return s1[i] === s2[j] && s1[j] === s2[i];
}

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.size() > 2) return false;
        }
    }
    if (diff.isEmpty()) return true;
    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);
}

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

Explanation

The key insight is that a single swap inside one string changes the characters at exactly two positions (or zero, if you swap an index with itself). So instead of trying swaps, we just compare the strings position by position and count where they disagree.

Walk both strings together and collect every index i where s1[i] != s2[i] into a list diff. Three or more mismatches can never be repaired by one swap, so the loop bails out with false as soon as a third mismatch appears.

After the scan there are only three cases. If diff is empty the strings are already equal — answer true with zero swaps. If diff has exactly one index, a swap would disturb a second, currently-matching position, so the answer is false. If diff has exactly two indices i and j, the swap of s1[i] and s1[j] fixes both spots only when the pairs cross-match: s1[i] == s2[j] and s1[j] == s2[i].

Default example: s1 = "bank", s2 = "kanb". Index 0 mismatches ('b' vs 'k'), indices 1 and 2 match, index 3 mismatches ('k' vs 'b'). With diff = [0, 3] we test the cross condition: s1[0]='b' equals s2[3]='b' and s1[3]='k' equals s2[0]='k', so one swap works and the answer is true.

The scan touches each character once, so the time is O(n) for strings of length n. The diff list never holds more than three indices thanks to the early exit, so the extra space is O(1).

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