💬 Discord
Sign In
NeetCode #767LC-1790EasyGreedy
← Back to All Problems

#767 · #1790 · Check if One String Swap Can Make Strings Equal(仅执行一次字符串交换能否使两个字符串相等)

📌 Problem Statement & Constraints

You are given two strings s1 and s2 of equal length. You may swap exactly two characters at indices i and j (possibly i == j) in one of the strings. Return true if the strings can be made equal. Constraints: 1 <= s1.length, s2.length <= 100, both strings contain lowercase English letters.

💡 Core Algorithmic Approaches

  1. Collect all indices where the two strings differ.
  2. Zero differences means they are already equal, and swapping an index with itself keeps them equal -- return true.
  3. Exactly two differences can be fixed iff the characters cross-match: s1[i] == s2[j] and s1[j] == s2[i].
  4. Any other number of differences cannot be repaired by a single swap.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one scan to collect the mismatches.
💾 Space Complexity
O(1): at most a few mismatch indices are stored.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the zero-mismatch case: already-equal strings are valid because a swap with i == j is allowed.
  • Allowing more than two mismatches: a single swap fixes at most two positions.
  • Checking only that the multiset of characters matches: the two positions must cross-match exactly.
  • Requiring i != j: the problem explicitly permits swapping an index with itself.