Check if One String Swap Can Make Strings Equal
Can a single character swap on one string make the two equal? Count mismatch positions.
4 min read
strings
Problem#
Given two equal-length strings s1 and s2, return true iff they are already equal OR a single swap of two positions in one string makes them equal.
Examples#
s1 = "bank", s2 = "kanb"→true(swap positions 0 and 3 ins2).s1 = "attack", s2 = "defend"→false.s1 = "kelb", s2 = "kelb"→true.
Constraints#
1 <= s1.length <= 100, lowercase letters.
Hints#
Hint
Find all mismatch positions. The strings are swappable iff there are exactly 0 or exactly 2 mismatches with crossed equality.
Approach#
Scan both strings. Collect mismatch indices in a vector. Return true if mismatches.size() == 0, or if it equals 2 and s1[i] == s2[j] && s1[j] == s2[i] for the two indices.
Solution#
class Solution {public: bool areAlmostEqual(string s1, string s2) { if (s1.size() != s2.size()) return false; int a = -1, b = -1; for (int i = 0; i < (int)s1.size(); ++i) { if (s1[i] != s2[i]) { if (a == -1) a = i; else if (b == -1) b = i; else return false; } } if (a == -1) return true; // strings equal if (b == -1) return false; // exactly one mismatch return s1[a] == s2[b] && s1[b] == s2[a]; }};func areAlmostEqual(s1 string, s2 string) bool { if len(s1) != len(s2) { return false } a, b := -1, -1 for i := 0; i < len(s1); i++ { if s1[i] != s2[i] { if a == -1 { a = i } else if b == -1 { b = i } else { return false } } } if a == -1 { return true } if b == -1 { return false } return s1[a] == s2[b] && s1[b] == s2[a]}class Solution: def areAlmostEqual(self, s1: str, s2: str) -> bool: if len(s1) != len(s2): return False a, b = -1, -1 for i in range(len(s1)): if s1[i] != s2[i]: if a == -1: a = i elif b == -1: b = i else: return False if a == -1: return True if b == -1: return False return s1[a] == s2[b] and s1[b] == s2[a]var areAlmostEqual = function(s1, s2) { if (s1.length !== s2.length) return false; let a = -1, b = -1; for (let i = 0; i < s1.length; i++) { if (s1[i] !== s2[i]) { if (a === -1) a = i; else if (b === -1) b = i; else return false; } } if (a === -1) return true; if (b === -1) return false; return s1[a] === s2[b] && s1[b] === s2[a];};class Solution { public boolean areAlmostEqual(String s1, String s2) { if (s1.length() != s2.length()) return false; int a = -1, b = -1; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) != s2.charAt(i)) { if (a == -1) a = i; else if (b == -1) b = i; else return false; } } if (a == -1) return true; if (b == -1) return false; return s1.charAt(a) == s2.charAt(b) && s1.charAt(b) == s2.charAt(a); }}function areAlmostEqual(s1: string, s2: string): boolean { if (s1.length !== s2.length) return false; let a = -1, b = -1; for (let i = 0; i < s1.length; i++) { if (s1[i] !== s2[i]) { if (a === -1) a = i; else if (b === -1) b = i; else return false; } } if (a === -1) return true; if (b === -1) return false; return s1[a] === s2[b] && s1[b] === s2[a];}Editorial#
A swap touches exactly two indices, so the only valid mismatch counts are 0 (no swap needed) or 2 (one swap fixes both). Anything else cannot be fixed by a single swap. Constant memory; one pass.
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#