Check if single swap can make strings equal
You are given two strings s1 and s2. Return true if a single swap can make strings equal. We have to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.
Note: A string swap is an operation where you choose two indices in a string and swap the characters at these indices.
Example 1:
Input: s1 = "bank", s2 = "kanb" Output: true Explanation: For example, swap the first character(k) with the last character(b) of s2 to make "bank".
Example 2:
Input: s1 = "attach", 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.
Approach:
Let’s take example 1. Index 0 and Index 3 of the strings “bank” and “kanb” do not match. The total no of mismatches is 2. If the no. of mismatch is 2 a single swap can make strings equal. We store and compare the mismatched characters. Base cases of the problem are,
- If two strings have different lengths, return false.
- When no.of.mismatch exceeds 2, the strings cannot be made equal with one swap.
- When no.of.mismatch is 0, then already strings are equal
- When no.of.mismatch is 1(Ex: s1=”Car” s2=”Cat“), then swap is not possible
Program
public boolean areAlmostEqual(String s1, String s2)
{
//Two strings have different lengths, can't be made equal with swap
if(s1.length() != s2.length())
return false;
//To store the mismatched characters in each string, Atmost 2 mismatched character allowed in each string.
char[] ch1 = new char[2];
char[] ch2 = new char[2];
int j = 0, noOfMismatch = 0;
for(int i =0; i<s1.length(); i++)
{
if(s1.charAt(i) != s2.charAt(i))
{
noOfMismatch++;
if(noOfMismatch >2 )
return false;
ch1[j] = s1.charAt(i);
ch2[j] = s2.charAt(i);
j++;
}
}
//Compare the mismatched characters and check if swap can make strings equal
//Example 1 : s1 = "bank", s2 = "kanb"
// ch1[0] = 'b' & ch2[1] = 'b'
// ch1[1] = 'k' & ch2[0] ='k'
return noOfMismatch == 0 || (noOfMismatch == 2 && (ch1[0] == ch2[1]) && (ch1[1] == ch2[0]) );
}
Complexity
Time Complexity – O(n) since we traverse the input array of length n only once
Space Complexity – O(1) constant space is used
