Minimum number of operations required to make two strings equal | Java 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 answer in this vector ; Traversing Strings ; If they have different parents ; Find their respective parents and merge them ; Store this in our Answer vector ; Number of operations ; Driver Code ; Two Strings S1 and S2 ; Function call
import java . util . * ; class GFG { static final int MAX = 500001 ; static int [ ] parent = new int [ MAX ] ; static int [ ] Rank = new int [ MAX ] ; static class pair { char first , second ; public pair ( char first , char second ) { this . first = first ; this . second = second ; } } static int find ( int x ) { return parent [ x ] = parent [ x ] == x ? x : find ( parent [ x ] ) ; } static void merge ( int r1 , int r2 ) { if ( r1 != r2 ) { if ( Rank [ r1 ] > Rank [ r2 ] ) { parent [ r2 ] = r1 ; Rank [ r1 ] += Rank [ r2 ] ; } else { parent [ r1 ] = r2 ; Rank [ r2 ] += Rank [ r1 ] ; } } } static void minimumOperations ( String s1 , String s2 ) { for ( int i = 1 ; i <= 26 ; i ++ ) { parent [ i ] = i ; Rank [ i ] = 1 ; } Vector < pair > ans = new Vector < pair > ( ) ; for ( int i = 0 ; i < s1 . length ( ) ; i ++ ) { if ( s1 . charAt ( i ) != s2 . charAt ( i ) ) { if ( find ( s1 . charAt ( i ) - 96 ) != find ( s2 . charAt ( i ) - 96 ) ) { int x = find ( s1 . charAt ( i ) - 96 ) ; int y = find ( s2 . charAt ( i ) - 96 ) ; merge ( x , y ) ; ans . add ( new pair ( s1 . charAt ( i ) , s2 . charAt ( i ) ) ) ; } } } System . out . print ( ans . size ( ) + "NEW_LINE"); for ( int i = 0 ; i < ans . size ( ) ; i ++ ) System . out . print ( ans . get ( i ) . first + " - > " + ans . get ( i ) . second + "NEW_LINE"); } public static void main ( String [ ] args ) { String s1 , s2 ; s1 = " abb " ; s2 = " dad " ; minimumOperations ( s1 , s2 ) ; } }