LeetCode 1790 - Check if One String Swap Can Make Strings Equal

The problem asks us to determine if two strings of equal length, s1 and s2, can be made identical by performing at most one string swap on exactly one of the strings. A string swap allows exchanging any two characters at different or same indices.

leetcodeeasyhash-tablestringcounting

LeetCode Problem 1790

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to determine if two strings of equal length, s1 and s2, can be made identical by performing at most one string swap on exactly one of the strings. A string swap allows exchanging any two characters at different or same indices. The task is not to perform multiple swaps or swaps on both strings, but a single swap on one string.

The input strings are composed solely of lowercase English letters and have lengths between 1 and 100. The output is a boolean: true if it is possible to make the strings equal using one or zero swaps, false otherwise.

Important observations include: if the strings are already identical, no swap is needed, so the answer is true. If the strings differ in more than two positions, a single swap cannot resolve all differences, so the answer is false. If they differ in exactly two positions, a swap may work, but the mismatched characters must align such that swapping them resolves the difference. Differences in only one position cannot be fixed with a single swap since one swap affects two characters. Edge cases include strings of length 1, strings with repeated characters, and already identical strings.

Approaches

The brute-force approach would try swapping every possible pair of characters in s1 and checking if the result equals s2. This guarantees correctness because it exhaustively tests all possible swaps, but its time complexity is O(n^2) for the swaps and O(n) for string comparison, resulting in O(n^3) overall. For n up to 100, this is technically feasible but inefficient and unnecessary given the problem constraints.

The optimal approach relies on observing the differences between s1 and s2. If we record indices where the characters differ:

  1. If there are zero differences, the strings are already equal.
  2. If there are exactly two differences, swapping the mismatched characters in one string may make the strings equal if the characters match in cross positions.
  3. Any other number of differences (one or more than two) cannot be fixed with a single swap.

This approach scans the strings once, records mismatched positions, and verifies the swap possibility, achieving O(n) time complexity and O(1) extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Try all possible swaps and compare strings
Optimal O(n) O(1) Track mismatched positions and validate a single swap

Algorithm Walkthrough

  1. Initialize an empty list diffs to store indices where s1[i] != s2[i].
  2. Iterate through the strings from index 0 to n-1:
  • If s1[i] != s2[i], append i to diffs.
  1. After iteration, check the length of diffs:
  • If 0, return true because the strings are already equal.
  • If 2, retrieve the indices i and j from diffs. Check if s1[i] == s2[j] and s1[j] == s2[i]. Return true if both conditions hold; otherwise, return false.
  • For any other length, return false because a single swap cannot resolve the differences.

Why it works: The algorithm guarantees correctness because a valid swap can only fix exactly two mismatched positions. Zero differences require no action. Any other number of differences cannot be corrected with one swap, so the conditions precisely capture all possible scenarios.

Python Solution

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        diffs = []
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                diffs.append(i)
                if len(diffs) > 2:  # early exit if more than 2 differences
                    return False
        
        if not diffs:
            return True
        if len(diffs) == 2:
            i, j = diffs
            return s1[i] == s2[j] and s1[j] == s2[i]
        return False

The code iterates through both strings simultaneously, collecting indices where characters differ. It leverages an early exit if differences exceed two. It then checks the conditions for a valid swap if exactly two differences exist. Finally, it handles the zero-difference case.

Go Solution

func areAlmostEqual(s1 string, s2 string) bool {
    diffs := []int{}
    for i := 0; i < len(s1); i++ {
        if s1[i] != s2[i] {
            diffs = append(diffs, i)
            if len(diffs) > 2 {
                return false
            }
        }
    }
    
    if len(diffs) == 0 {
        return true
    }
    if len(diffs) == 2 {
        i, j := diffs[0], diffs[1]
        return s1[i] == s2[j] && s1[j] == s2[i]
    }
    return false
}

The Go solution mirrors the Python logic, using a slice to track differences. Early exit prevents unnecessary comparisons, and swapping logic is handled directly with index comparison.

Worked Examples

Example 1

Input: s1 = "bank", s2 = "kanb"

i s1[i] s2[i] diffs
0 b k [0]
1 a a [0]
2 n n [0]
3 k b [0, 3]

Swap check: s1[0] == s2[3] and s1[3] == s2[0] → b == b and k == k → true

Output: true

Example 2

Input: s1 = "attack", s2 = "defend"

Number of differences > 2 → return false

Output: false

Example 3

Input: s1 = "kelb", s2 = "kelb"

No differences → return true

Output: true

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the strings to record differences
Space O(1) At most two indices are stored, independent of n

This solution is optimal given the constraints because storing differences requires minimal space and scanning once suffices.

Test Cases

# test cases
assert Solution().areAlmostEqual("bank", "kanb") == True  # swap first and last
assert Solution().areAlmostEqual("attack", "defend") == False  # multiple differences
assert Solution().areAlmostEqual("kelb", "kelb") == True  # already equal
assert Solution().areAlmostEqual("a", "a") == True  # single character, same
assert Solution().areAlmostEqual("a", "b") == False  # single character, different
assert Solution().areAlmostEqual("abcd", "abdc") == True  # swap middle characters
assert Solution().areAlmostEqual("abcd", "abcd") == True  # no swap needed
assert Solution().areAlmostEqual("abcd", "abcf") == False  # one character mismatch
Test Why
"bank", "kanb" Valid swap at edges
"attack", "defend" Multiple differences, impossible
"kelb", "kelb" Strings identical, no swap needed
"a", "a" Minimum length, identical
"a", "b" Minimum length, different
"abcd", "abdc" Swap in the middle works
"abcd", "abcd" Already equal
"abcd", "abcf" Single mismatch cannot be fixed

Edge Cases

One edge case is when the strings are already equal. The algorithm handles this by returning true when no differences are found. Another case is when strings differ in exactly one position; a single swap cannot fix this, so the algorithm correctly returns false. Finally, strings with repeated characters may allow a swap to succeed even if characters repeat in the string. The solution accounts for this because it checks the specific character positions for a valid swap rather than relying on frequency counts. These edge cases are naturally handled by the simple difference tracking and conditional logic.