1790. Check if One String Swap Can Make Strings Equal
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 60.8%
Problem Breakdown
We are given two strings s1 and s2 of equal length. The task is to determine if it’s possible to make both strings equal by performing at most one string swap on exactly one of the strings. A string swap involves choosing two indices in a string and swapping the characters at these indices.
Inputs:
- Two strings
s1ands2of equal length.
Outputs:
- Return
trueif it’s possible to make both strings equal with at most one swap; otherwise, returnfalse.
Implicit Constraints or Edge Cases:
- If the strings are already identical, no swap is needed.
- If more than two characters differ between the strings, more than one swap would be required.
- The strings consist of only lowercase English letters.
Intuition
The brute-force approach would involve generating all possible swaps in s1 and checking if any of them match s2. However, this is inefficient with a time complexity of O(n^2) due to the nested loops for generating swaps.
A better approach involves identifying the positions where the characters differ between s1 and s2. If there are exactly two such positions, we can check if swapping these characters in one of the strings makes them equal. If there are more than two or zero differences, it’s impossible to make the strings equal with just one swap.
Approach
- Initialize a list to store the indices where the characters differ between
s1ands2. - Iterate through both strings simultaneously:
- If the characters at the current index are different, add the index to the list.
- After the iteration:
- If the list of differing indices is empty, the strings are already equal.
- If the list has exactly two indices, check if swapping these characters in one of the strings makes them equal.
- If the list has more than two or zero indices, return
false.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the strings. We iterate through both strings once to find differing indices.
- Space Complexity: O(1) for storing the indices of differing characters (at most 2).
Solution
def areAlmostEqual(s1: str, s2: str) -> bool:
# List to store indices where characters differ
diff_indices = []
# Iterate through both strings
for i in range(len(s1)):
if s1[i] != s2[i]:
diff_indices.append(i)
# If more than two differences, return False early
if len(diff_indices) > 2:
return False
# If no differences or exactly two differences that can be swapped
return len(diff_indices) == 0 or (len(diff_indices) == 2 and s1[diff_indices[0]] == s2[diff_indices[1]] and s1[diff_indices[1]] == s2[diff_indices[0]])
Edge Cases Handled
- Identical Strings: If
s1ands2are already equal, the function returnstrue. - No Possible Swap: If more than two characters differ between
s1ands2, the function returnsfalse. - Single Swap Needed: If exactly two characters differ and swapping them makes the strings equal, the function returns
true.
The solution provided is correct, efficient, and clear. It handles all edge cases as described in the problem statement.