Minimum number of operations required to make two strings equal | Python3 implementation to find the minimum number of operations to make two strings equal ; Function to find out parent of an alphabet ; Function to merge two different alphabets ; Merge a and b using rank compression ; Function to find the minimum number of operations required ; Initializing parent to i and rank ( size ) to 1 ; We will store our answerin this list ; Traversing strings ; If they have different parents ; Find their respective parents and merge them ; Store this in our Answer list ; Number of operations ; Driver code ; Two strings S1 and S2 ; Function Call
MAX = 500001 NEW_LINE parent = [ 0 ] * MAX NEW_LINE Rank = [ 0 ] * MAX NEW_LINE def find ( x ) : NEW_LINE INDENT if parent [ x ] == x : NEW_LINE INDENT return x NEW_LINE DEDENT else : NEW_LINE INDENT return find ( parent [ x ] ) NEW_LINE DEDENT DEDENT def merge ( r1 , r2 ) : NEW_LINE INDENT if ( r1 != r2 ) : NEW_LINE INDENT if ( Rank [ r1 ] > Rank [ r2 ] ) : NEW_LINE INDENT parent [ r2 ] = r1 NEW_LINE Rank [ r1 ] += Rank [ r2 ] NEW_LINE DEDENT else : NEW_LINE INDENT parent [ r1 ] = r2 NEW_LINE Rank [ r2 ] += Rank [ r1 ] NEW_LINE DEDENT DEDENT DEDENT def minimumOperations ( s1 , s2 ) : NEW_LINE INDENT for i in range ( 1 , 26 + 1 ) : NEW_LINE INDENT parent [ i ] = i NEW_LINE Rank [ i ] = 1 NEW_LINE DEDENT ans = [ ] NEW_LINE for i in range ( len ( s1 ) ) : NEW_LINE INDENT if ( s1 [ i ] != s2 [ i ] ) : NEW_LINE INDENT if ( find ( ord ( s1 [ i ] ) - 96 ) != find ( ord ( s2 [ i ] ) - 96 ) ) : NEW_LINE INDENT x = find ( ord ( s1 [ i ] ) - 96 ) NEW_LINE y = find ( ord ( s2 [ i ] ) - 96 ) NEW_LINE merge ( x , y ) NEW_LINE ans . append ( [ s1 [ i ] , s2 [ i ] ] ) NEW_LINE DEDENT DEDENT DEDENT print ( len ( ans ) ) NEW_LINE for i in ans : NEW_LINE INDENT print ( i [ 0 ] , " - > " , i [ 1 ] ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s1 = " abb " NEW_LINE s2 = " dad " NEW_LINE minimumOperations ( s1 , s2 ) NEW_LINE DEDENT