Check if One String Swap Can Make Strings Equal

Difficulty: Easy | Acceptance: 49.50% | Paid: No Topics: Hash Table, String, Counting

You are given two strings s1 and s2 of equal length. 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.

A string swap is choosing two indices in a string (not necessarily different) and swapping the characters at these indices.

• Examples
• Constraints
• Single Pass Comparison
• Frequency Counting

Examples

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s1 to make "bank" equal to "kanb".

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The strings are already equal, so no swap is needed.

Constraints

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

Single Pass Comparison

Intuition We can iterate through both strings simultaneously to find the indices where the characters differ. If there are exactly two differences, we check if swapping the characters at these indices in one string would make it equal to the other.

Steps

• If the strings are already identical, return true.
• Iterate through the strings and record the indices where characters differ.
• If the number of differing indices is not exactly 2, return false.
• Check if swapping the characters at the two differing indices makes the strings equal.

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        diff = []
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                diff.append(i)
                if len(diff) > 2:
                    return False
        return len(diff) == 2 and s1[diff[0]] == s2[diff[1]] and s1[diff[1]] == s2[diff[0]]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: We only store a few integer indices, so space complexity is constant.

Frequency Counting

Intuition For two strings to be equal with at most one swap, they must be anagrams of each other (contain the same characters with the same frequencies). Additionally, the number of positions where they differ must be 0 or 2.

Steps

• Count the frequency of each character in both strings.
• If the frequency counts differ, return false.
• Count the number of indices where the characters in s1 and s2 differ.
• Return true if the number of differing indices is 0 or 2.

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        if len(s1) != len(s2):
            return False
        from collections import Counter
        if Counter(s1) != Counter(s2):
            return False
        diff = 0
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                diff += 1
                if diff > 2:
                    return False
        return diff == 2

Complexity

• Time: O(n)
• Space: O(1)
• Notes: The space complexity is constant because the frequency array size is fixed at 26 (for lowercase English letters).