Check if One String Swap Can Make Strings Equal - Solution & Explanation
Problem Statement
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.lengths1ands2consist of only lowercase English letters.
Approach Overview
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 1: Counting Mismatches and Swapping
Approach: This approach involves iterating through the strings and identifying the positions where the characters differ (mismatch). If the number of mismatched positions is zero, the strings are already equal. If there are exactly two mismatched character positions (i, j), you check if swapping the characters at these positions in one of the strings makes the two strings equal.
In this C solution, we traverse the strings s1 and s2 to find mismatches. If there are exactly two mismatches, we check if swapping these positions in one string results in equality. The solution returns true if that's the case or false otherwise.
Complexity
Time Complexity: O(n), where n is the length of the strings. Space Complexity: O(1), no additional space is used other than two integer indices.
Approach 2: Permutation Check on Two Mismatches
Approach: If there are two mismatches in the strings, check if swapping these characters in one string equals two mismatched positions in the other string. Additionally, ensure they are permutations of each other since that validates the swap correctness for larger strings and edge cases.
This C solution leverages a character frequency check (permutation check) to validate that the strings can potentially be made equal. Then it checks mismatched indices as before.
Complexity
Time Complexity: O(n). Space Complexity: O(1) due to the use of fixed arrays for the permutation check.
Approach 3: Counting
We use a variable cnt to record the number of characters at the same position in the two strings that are different. If the two strings meet the requirements of the problem, then cnt must be 0 or 2. We also use two character variables c1 and c2 to record the characters that are different at the same position in the two strings.
While traversing the two strings simultaneously, for two characters a and b at the same position, if a \ne b, then cnt is incremented by 1. If at this time cnt is greater than 2, or cnt is 2 and a \ne c2 or b \ne c1, then we directly return false. Note to record c1 and c2.
At the end of the traversal, if cnt neq 1, return true.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Counting Mismatches and Swapping | Time Complexity: O(n), where n is the length of the strings. Space Complexity: O(1), no additional space is used other than two integer indices. |
| Permutation Check on Two Mismatches | Time Complexity: O(n). Space Complexity: O(1) due to the use of fixed arrays for the permutation check. |
| Counting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Check if One String Swap Can Make Strings Equal - Leetcode 1790 - Python • NeetCodeIO • 8,435 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if One String Swap Can Make Strings Equal easy or hard?
Check if One String Swap Can Make Strings Equal Python/Java solution
How to solve Check if One String Swap Can Make Strings Equal in O(n)?
What is the best approach for Check if One String Swap Can Make Strings Equal?
Is Check if One String Swap Can Make Strings Equal asked at Google/Amazon/Meta?
What data structure is used in Check if One String Swap Can Make Strings Equal?
What is the time complexity of Check if One String Swap Can Make Strings Equal?
Ready to solve this problem?
Practice Check if One String Swap Can Make Strings Equal with our built-in code editor and test cases.
Practice on FleetCode