1790.Check_if_One_String_Swap_Can_Make_Strings_Equal(Easy).md

1790. Check if One String Swap Can Make Strings Equal (Easy)

Date and Time: Feb 5, 2025, 19:50 (EST)

Link: https://leetcode.com/problems/check-if-one-string-swap-can-make-strings-equal

Question:

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 1:

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

Output: true

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

Example 2:

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

Output: false

Explanation: It is impossible to make them equal with one string swap.

Example 3:

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

Output: true

Explanation: The two strings are already equal, so no string swap operation is required.

Edge Case:

Input: s1 = "s", s2 = "b"

Output: false

Edge Case:

Input: s1 = "sb", s2 = "bk"

Output: false

Constraints:

• 1 <= s1.length, s2.length <= 100

• s1.length == s2.length

• s1 and s2 consist of only lowercase English letters.

Walk-through:

Use ptrs i, j to record what indices are different and counts to check if counts == 0 or 2, these are the only two scenarios that are possible to return True. If counts == 2, we need to check if s1[i]==s2[j] and s2[i] == s1[j], so that means one string can swap two indices to be the same of another string.

Python Solution:

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        # Use three variables i, j, counts to record the indices. If counts != 0 or 2, we should return False. If counts == 2, check if s1[i] == s2[j] and s1[j] == s2[i]

        # TC: O(n), SC: O(1)
        i, j = -1, -1
        counts = 0
        for k in range(len(s1)):
            if s1[k] != s2[k]:
                counts += 1
                if i == -1:
                    i = k
                elif j == -1:
                    j = k
        # Check counts and indices
        if counts == 0:
            return True
        elif counts == 2 and s1[i] == s2[j] and s2[i] == s1[j]:
            return True
        return False

Time Complexity: $O(n)$
Space Complexity: $O(1)$