Problem Statement & Formal Constraints

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.

Theoretical Framework: The Mismatch Invariant

To determine if at most one swap can reconcile two strings of equal length $N$, we observe two mathematical invariants:

1. Mismatch Cardinality: The number of mismatching indices $k$ where $s1[i] eq s2[i]$ must be either 0 or 2. If $k = 1$, a single swap cannot fix one character without disrupting another. If $k > 2$, one swap can at best reconcile two positions, leaving at least one mismatch unresolved.
2. Cross-Character Equality: If exactly two mismatches exist at indices $i$ and $j$, swapping the characters requires that $s1[i] == s2[j]$ and $s1[j] == s2[i]$.

Approach 1: Single-Pass Early-Exit in C++

By collecting mismatched indices into a fixed-capacity vector and terminating early the instant a third mismatch is encountered, we avoid scanning the remainder of the string:

#include <string>
#include <vector>

class Solution {
public:
    bool areAlmostEqual(const std::string& s1, const std::string& s2) {
        if (s1 == s2) return true;

        std::vector<int> diffIndices;
        diffIndices.reserve(3);

        for (int i = 0; i < s1.length(); ++i) {
            if (s1[i] != s2[i]) {
                diffIndices.push_back(i);
                // Early exit: impossible to resolve with 1 swap if mismatches > 2
                if (diffIndices.size() > 2) {
                    return false;
                }
            }
        }

        // Must have exactly 2 mismatches with cross-equal characters
        if (diffIndices.size() == 2) {
            int i = diffIndices[0];
            int j = diffIndices[1];
            return s1[i] == s2[j] && s1[j] == s2[i];
        }

        return false;
    }
};

Approach 2: TypeScript Solution with Primitive Integer Pointers

In TypeScript, we eliminate array allocations entirely by using two primitive integer variables to store the mismatch indices:

/**
 * Determines whether two strings can be made equal with at most one swap.
 * Time Complexity: O(N) single-pass with early exit
 * Space Complexity: O(1) auxiliary variables
 */
export function areAlmostEqual(s1: string, s2: string): boolean {
  if (s1 === s2) return true;

  let firstMismatch = -1;
  let secondMismatch = -1;

  for (let i = 0; i < s1.length; i++) {
    if (s1[i] !== s2[i]) {
      if (firstMismatch === -1) {
        firstMismatch = i;
      } else if (secondMismatch === -1) {
        secondMismatch = i;
      } else {
        // Third mismatch encountered: early exit
        return false;
      }
    }
  }

  // Exactly two mismatches must cross-match
  if (secondMismatch !== -1) {
    return s1[firstMismatch] === s2[secondMismatch] && 
           s1[secondMismatch] === s2[firstMismatch];
  }

  return false;
}

Complexity Evaluation Matrix

Comparing execution strategies for LeetCode 1790:

Real-World Full-Stack Engineering Applications

Single-swap verification patterns apply broadly across distributed software systems:

• Typo-Tolerance in Search Autocomplete: Detecting 1-transposition typing errors (e.g., typing "teh" instead of "the") in search queries before dispatching database lookups.
• Hamming & Levenshtein Distance Pruning: In genome sequencing or spell checkers, rapidly ruling out candidate strings whose substitution distance exceeds 1 without computing full $O(N imes M)$ dynamic programming matrices.
• Network Packet Checksum Validation: Detecting bit flip transpositions across data frames in custom UDP transmission protocols.

Frequently Asked Questions

Why is it impossible to fix the strings if exactly one mismatch exists?

A string swap takes two indices. Swapping an index with itself leaves the string unchanged (0 swaps). Swapping two different indices changes both characters. If only one index is incorrect, changing any other index introduces a new mismatch, making equality impossible.

Does this algorithm handle strings containing identical characters like "aa" and "aa"?

Yes. If strings are identical, the initial check if (s1 === s2) return true returns immediately in $O(1)$ or $O(N)$ without entering the mismatch loop.

What is the benefit of primitive indices over array storage in JavaScript?

Using primitive numbers (firstMismatch, secondMismatch) avoids allocating a JavaScript Array object on the V8 heap, eliminating garbage collector overhead completely.

Can this algorithm be vectorized with SIMD instructions?

Yes. In C++, AVX-512 can compare 64 characters per clock cycle using _mm512_cmpeq_epi8_mask, identifying mismatch bitmasks in sub-nanosecond time.

Conclusion & Performance Takeaways

LeetCode 1790 demonstrates the importance of invariant analysis in software engineering. By recognizing that valid swaps require exactly 0 or 2 mismatches with cross-matching characters, we achieve an optimal $O(N)$ time and $O(1)$ space solution with zero allocations.