Check if One String Swap Can Make Strings Equal — Solution
Check if One String Swap Can Make Strings Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check if One String Swap Can Make Strings Equal is an easy coding problem on strings, hash table and counting, asked in Amazon and Meta interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two lowercase strings s1 and s2 of the same length. A string swap picks two indices of one string (not necessarily different) and exchanges the characters at them.
Return true if you can make the two strings equal by performing at most one string swap on exactly one of them, and false otherwise.
Example 1
Input: s1 = "kairo", s2 = "kiaro"
Output: true
Explanation: Swap `a` and `i` in `s1`.
Example 2
Input: s1 = "code", s2 = "dcoe"
Output: false
Explanation: Three positions differ; one swap fixes at most two.
Example 3
Input: s1 = "bug", s2 = "bug"
Output: true
Explanation: No swap needed.
Constraints
1 <= s1.length, s2.length <= 100s1.length == s2.lengths1 and s2 consist of only lowercase English letters
Hints for Check if One String Swap Can Make Strings Equal
Hint 1
Look at the indices where the two strings differ.
Hint 2
One swap changes at most two positions, so more than two differences is hopeless — and so is exactly one.
Hint 3
With exactly two differing indices
iandj, a swap works only ifs1[i] == s2[j]ands1[j] == s2[i].
How to solve Check if One String Swap Can Make Strings Equal
A swap touches two positions, so the strings must already agree everywhere except at zero or two indices, and those two must be each other's mirror image.
Approach
- Collect the indices where
s1[k] != s2[k], stopping early once there are three. - No differences →
true. - Exactly two differences
i < j→ return whethers1[i] == s2[j]ands1[j] == s2[i]. - Any other count →
false.
Why it works
Swapping positions i and j in s1 changes only those two characters. Every mismatch outside {i, j} therefore survives, so all mismatches must lie in {i, j}; a single mismatch cannot be fixed because the swap would have to bring in a character from a matching position and break it. With two mismatches the swap fixes both exactly when the characters are crossed. Swapping in s2 instead is symmetric.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Equal strings need no swap and return
true. - Equal character counts are not enough —
"abcd"and"badc"need two swaps. - Exactly one mismatch is always
false.
Reference solution
Python
def areAlmostEqual(s1: str, s2: str) -> bool:
diff = [i for i in range(len(s1)) if s1[i] != s2[i]]
if not diff:
return True
if len(diff) != 2:
return False
i, j = diff
return s1[i] == s2[j] and s1[j] == s2[i]Java
public static boolean areAlmostEqual(String s1, String s2) {
int[] d = new int[2];
int k = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
if (k == 2) return false;
d[k++] = i;
}
}
if (k == 0) return true;
if (k == 1) return false;
return s1.charAt(d[0]) == s2.charAt(d[1]) && s1.charAt(d[1]) == s2.charAt(d[0]);
}C++
bool areAlmostEqual(string s1, string s2) {
vector<int> d;
for (int i = 0; i < (int)s1.size(); i++) {
if (s1[i] != s2[i]) {
if (d.size() == 2) return false;
d.push_back(i);
}
}
if (d.empty()) return true;
if (d.size() == 1) return false;
return s1[d[0]] == s2[d[1]] && s1[d[1]] == s2[d[0]];
}JavaScript
var areAlmostEqual = function(s1, s2) {
var diff = [];
for (var k = 0; k < s1.length; k++) {
if (s1[k] !== s2[k]) {
if (diff.length === 2) return false;
diff.push(k);
}
}
if (diff.length === 0) return true;
if (diff.length === 1) return false;
var i = diff[0], j = diff[1];
return s1[i] === s2[j] && s1[j] === s2[i];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets