Check if One String Swap Can Make Strings Equal — LeetCode 1790 Python Solution

The problem

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.

Example

Input

s1 = "bank", s2 = "kanb"

Output

true

Explanation

For example, swap the first character with the last character of s2 to make "bank".

Python solution

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        cnt = 0
        c1 = c2 = None
        for a, b in zip(s1, s2):
            if a != b:
                cnt += 1
                if cnt > 2 or (cnt == 2 and (a != c2 or b != c1)):
                    return False
                c1, c2 = a, b
        return cnt != 1

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1790. Check if One String Swap Can Make Strings Equal is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems