Minimum number of pairs required to make two strings same | C ++ implementation of the approach ; Function which will check if there is a path between a and b by using BFS ; Function to return the minimum number of pairs ; To store the count of pairs ; Iterating through the strings ; Check if we can add an edge in the graph ; Return the count of pairs ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool checkPath ( char a , char b , map < char , vector < char > > & G ) { map < char , bool > visited ; deque < char > queue ; queue . push_back ( a ) ; visited [ a ] = true ; while ( ! queue . empty ( ) ) { int n = queue . front ( ) ; queue . pop_front ( ) ; if ( n == b ) return true ; for ( auto i : G [ n ] ) { if ( visited [ i ] == false ) { queue . push_back ( i ) ; visited [ i ] = true ; } } } return false ; } int countPairs ( string s1 , string s2 , map < char , vector < char > > & G , int x ) { int count = 0 ; for ( int i = 0 ; i < x ; i ++ ) { char a = s1 [ i ] ; char b = s2 [ i ] ; if ( G . find ( a ) != G . end ( ) and G . find ( b ) == G . end ( ) and a != b ) { G [ a ] . push_back ( b ) ; G [ b ] . push_back ( a ) ; count ++ ; } else if ( G . find ( b ) != G . end ( ) and G . find ( a ) == G . end ( ) and a != b ) { G [ b ] . push_back ( a ) ; G [ a ] . push_back ( b ) ; count ++ ; } else if ( G . find ( a ) == G . end ( ) and G . find ( b ) == G . end ( ) and a != b ) { G [ a ] . push_back ( b ) ; G [ b ] . push_back ( a ) ; count ++ ; } else { if ( ! checkPath ( a , b , G ) and a != b ) { G [ a ] . push_back ( b ) ; G [ b ] . push_back ( a ) ; count ++ ; } } } return count ; } int main ( ) { string s1 = " abb " , s2 = " dad " ; int x = s1 . length ( ) ; map < char , vector < char > > G ; cout << countPairs ( s1 , s2 , G , x ) << endl ; return 0 ; }