Problem Statement
Brute Force [Accepted]
class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
diff = 0
swap_s1 = set()
swap_s2 = set()
for a, b in zip(s1, s2):
if a != b:
swap_s1.add(a)
swap_s2.add(b)
diff += 1
if diff > 2:
return False
if diff == 1 or len(swap_s1) != len(swap_s2):
return False
for c in swap_s1:
if c not in swap_s2:
return False
return True
Editorial
Approach 1: Frequency Map + Check Differences
class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
if s1 == s2:
return True
s1_frequency_map = [0] * 26
s2_frequency_map = [0] * 26
num_diffs = 0
for i in range(len(s1)):
s1_char = s1[i]
s2_char = s2[i]
if s1_char != s2_char:
num_diffs += 1
# num_diffs is more than 2, one string swap will not make two strings equal
if num_diffs > 2:
return False
# increment frequencies
s1_frequency_map[ord(s1_char) - ord("a")] += 1
s2_frequency_map[ord(s2_char) - ord("a")] += 1
# check if frequencies are equal
return s1_frequency_map == s2_frequency_map
Approach 2: Only Check Differences
class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
first_index_diff = 0
second_index_diff = 0
num_diffs = 0
for i in range(len(s1)):
if s1[i] != s2[i]:
num_diffs += 1
# num_diffs is more than 2, one string swap will not make two strings equal
if num_diffs > 2:
return False
elif num_diffs == 1:
# store the index of first difference
first_index_diff = i
else:
# store the index of second difference
second_index_diff = i
# check if swap is possible
return (
s1[first_index_diff] == s2[second_index_diff]
and s1[second_index_diff] == s2[first_index_diff]
)
