Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

1
2
3

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Solution

Method 1 - Check where indices differ

To determine if we can make s1 equal to s2 by performing at most one swap on exactly one of the strings, we need to follow these steps:

  • If both strings are already equal, return true.
  • Identify the indices where s1 and s2 differ.
  • If there are exactly zero differences, return true.
  • If there are exactly two differences and swapping these indices in one of the strings would make the strings equal, return true.
  • Otherwise, return false.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        int first = -1, second = -1;
        int diffCount = 0;
        
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diffCount++;
                if (first == -1) {
                    first = i;
                } else {
                    second = i;
                }
                
                if (diffCount > 2) {
                    return false;
                }
            }
        }

        if (diffCount == 2 && 
	        s1.charAt(first) == s2.charAt(second) && s1.charAt(second) == s2.charAt(first)) {
            return true;
        }

        return diffCount == 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
	 def areAlmostEqual(s1: str, s2: str) -> bool:
	     first = -1
	     second = -1
	     diffCount = 0
	 
	     for i in range(len(s1)):
	         if s1[i] != s2[i]:
	             diffCount += 1
	             if first == -1:
	                 first = i
	             else:
	                 second = i
	             
	             if diffCount > 2:
	                 return False
	 
	     if diffCount == 2 and s1[first] == s2[second] and s1[second] == s2[first]:
	         return True
	 
	     return diffCount == 0

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the strings, for scanning the strings.
  • 🧺 Space complexity: O(1), for using a few variables to check and track changes.