Check if a string can be convert to another by swapping two characters

Table of contents

1. Introduction into the problem
2. Algorithm
3. Implementation

1. Introduction into the problem

Having two strings s1 and s2 equal in length of size n, you must check if they are equal after you swap any of two different characters. If strings are different on more than just 2 characters it must return false.

Example 1:

Input: s1 = "kanb", s2 = "bank"
Output: true

Example 2:

Input: s1 = "kanban", s2 = "balcan"
Output: false

Example 3:

Input: s1 = "equal", s2 = "equal"
Output: true

2. Algorithm

1. start by checking any of the string characters one by one with the other string
2. if characters are different store the index of the character in the string
3. if only two characters makes the difference then start swapping of them and do the comparation
   else if they are not already equals return false

Time comlexity of this algorithm is O(n) because we compare each character of the strings from 0 to n-1 even though we do only one swap in the best case.

Space complexity is O(n) as it requires an additional array to store the indexes of the different characters that in the worst case can be all of them.

3. Implementation

#include <iostream>

using namespace std;

bool areAlmostEqual(string s1, string s2) {
    int l1 = s1.length(), l2 = s2.length();
   
    int *idx = new int[l2], j=0, chr;
    
    if(1 < l1 && l1 == l2 ) 
      {
      for (int i=0; i<l2; i++)
        if (s1[i] != s2[i])
            idx[j++] = i;
      if (j == 2) 
        chr = s2[idx[0]],
        s2[idx[0]] = s2[idx[1]],
        s2[idx[1]] = chr;
      else
        if (s1.compare(s2) != 0)
            return false;
      }
      
    return !s1.compare(s2);    
}

/* v2
bool areAlmostEqual(string s1, string s2) {
    int l1 = s1.length(), l2 = s2.length();
   
    int i1=-1, i2=-1, i, j;
    
    char tmp;
    
    if(1 < l1 && l1 == l2 ) 
      {
      for (i=0, j=0; i < l2; i++)
        if (s1[i] != s2[i])
            {
                if (i1 == -1) i1 = i;
                else if (i2 == -1) i2 = i;
                j++;
            }
      if (j == 2) 
        tmp = s2[i1],
        s2[i1] = s2[i2],
        s2[i2] = tmp;
      else
        if (s1.compare(s2) != 0)
            return false;
      }
      
    return !s1.compare(s2);    
}
*/
int main()
{   bool sol = areAlmostEqual("kanb","bank");
    if (sol) cout<<"true";
    else cout<<"false";
    
    cout<<endl;
    
    sol = areAlmostEqual("kanban","balcan");
    if (sol) cout<<"true";
    else cout<<"false";
    return 0;
}

Output:

true
false

Step by step example
case 1: j will be 2, therefore s2 will be changed by swapping the 2 characters

    i	s1		s2	j	idx	=> 	s2 	=>	s1 == s2 = true  	
    0	(k 	==	b)	0	0		k
    1	(a	==	a)	1	3		a
    2	(n	==	n)	2			n
    3	(b	==	k)	3			b

case 2: j will be 3, therefore will be no swapping

    i	s1		s2	j	idx 	=> 	s2 	=>	s1 == s2 = false
    0	(k 	==	b)	0	0		b
    1	(a	==	a)	1	2		a
    2	(n	==	l)	2	3		l
    3	(b	==	c)	3			c
    4	(a	==	a)	4			a
    5	(n	==	n)	5			n

With this article at OpenGenus, you must have the complete idea of how to Check if a string can be convert to another by swapping two characters.