1790. Check if One String Swap Can Make Strings Equal

Problem Statement

link: LeetCode.cn LeetCode 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.

Example:

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

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

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

Constraints: 1 <= s1.length, s2.length <= 100 s1.length == s2.length s1 and s2 consist of only lowercase English letters.

Solution Approach

The solution determines if two strings can be made equal with a single swap by identifying differing indices and checking if swapping characters at these indices can make the strings identical.

Algorithm

1. Identify Mismatches: The solution iterates through the strings to find up to two indices where the characters differ.
2. Check Swap Validity: It then verifies if swapping the characters at these mismatched indices in one of the strings makes the two strings equal.
3. Handle Edge Cases: If there are no mismatches, the strings are already equal, and the solution returns true; if more than two mismatches are found, it returns false.

Complexity

time complexity: O(n) space complexity: O(C) C = 2

Implement

    class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        i = j = -1
        for idx, (x, y) in enumerate(zip(s1, s2)):
            if x != y:
                if i < 0:
                    i = idx
                elif j < 0:
                    j = idx
                else:
                    return False

        return i < 0 or j >= 0 and s1[i] == s2[j] and s1[j] == s2[i]
  

    
    

Twitter  facebook  Email