Check if single swap can make strings equal

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 stringsbank” 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

[code lang=”java”]

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]) );

}

[/code]

 

Complexity

Time Complexity – O(n) since we traverse the input array of length n only once

Space Complexity – O(1) constant space is used

You Might Also Like…

Count of each character in a string

C program for String Reversal | Samsung

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *