Watch 10 video solutions for Check if One String Swap Can Make Strings Equal, a easy level problem involving Hash Table, String, Counting. This walkthrough by NeetCodeIO has 8,253 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Constraints:
1 <= s1.length, s2.length <= 100s1.length == s2.lengths1 and s2 consist of only lowercase English letters.Problem Overview: Two strings s1 and s2 of equal length are given. Determine whether a single swap of two characters in one string can make both strings identical.
Approach 1: Counting Mismatches and Swapping (O(n) time, O(1) space)
Scan both strings once and record indices where characters differ. If there are more than two mismatches, a single swap cannot fix the strings. If exactly two mismatches exist at indices i and j, check whether swapping s1[i] and s1[j] makes the strings equal by verifying s1[i] == s2[j] and s1[j] == s2[i]. If there are zero mismatches, the strings are already equal and the answer is true. This approach works with a simple linear pass over the string, storing at most two indices, so the space usage stays constant.
Approach 2: Permutation Check on Two Mismatches (O(n) time, O(1) space)
Another way is to focus on the characters themselves instead of the indices. Iterate through both strings and collect characters that differ. If the mismatch list grows beyond two pairs, return false. When exactly two mismatches appear, check whether the pair forms a valid permutation: the first mismatch from s1 must match the second from s2 and vice versa. This treats the problem as a small permutation validation using ideas similar to hash table or counting checks, but with only two elements. The logic remains O(n) because each character is visited once.
Both strategies rely on the same key insight: only two positions can differ if a single swap is enough to fix the strings. Any additional mismatch immediately invalidates the condition. Because the algorithm performs a single pass with constant memory, it scales well even for long strings.
Recommended for interviews: The mismatch counting approach is the one interviewers typically expect. It demonstrates clear reasoning about constraints and avoids unnecessary data structures. Showing that you first detect mismatches and then validate the swap condition signals strong problem decomposition and clean O(n) implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Mismatches and Swapping | O(n) | O(1) | General case. Best approach for interviews and production due to simple logic. |
| Permutation Check on Two Mismatches | O(n) | O(1) | Useful when framing the problem as validating a small permutation of mismatched characters. |