Check whether two strings can be made equal by reversing substring of equal length from both strings | Java program for the above approach ; Function to count inversion count of the string ; For storing frequency ; Add all the characters which are less than the ith character before i . ; Adding the count to inversion count ; Updating the character in the frequency array ; Function to check whether any of the string have a repeated character ; Function to check whether the string S1 and S2 can be made equal by reversing sub strings of same size in both strings ; Frequency array to check whether both string have same character or not ; Adding the frequency ; ; If the character is not in S1 ; Decrementing the frequency ; If both string doesnot have same characters or not ; Finding inversion count of both strings ; If inversion count is same , or have same parity or if any of the string have a repeated character then the answer is Yes else No ; Driver Code
import java . io . * ; import java . util . * ; class GFG { static int inversionCount ( String s ) { int [ ] freq = new int [ 26 ] ; int inv = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { int temp = 0 ; for ( int j = 0 ; j < ( int ) ( s . charAt ( i ) - ' a ' ) ; j ++ ) temp += freq [ j ] ; inv += ( i - temp ) ; freq [ s . charAt ( i ) - ' a ' ] ++ ; } return inv ; } static boolean haveRepeated ( String S1 , String S2 ) { int [ ] freq = new int [ 26 ] ; for ( char i : S1 . toCharArray ( ) ) { if ( freq [ i - ' a ' ] > 0 ) return true ; freq [ i - ' a ' ] ++ ; } for ( int i = 0 ; i < 26 ; i ++ ) freq [ i ] = 0 ; for ( char i : S2 . toCharArray ( ) ) { if ( freq [ i - ' a ' ] > 0 ) return true ; freq [ i - ' a ' ] ++ ; } return false ; } static void checkToMakeEqual ( String S1 , String S2 ) { int [ ] freq = new int [ 26 ] ; for ( int i = 0 ; i < S1 . length ( ) ; i ++ ) { freq [ S1 . charAt ( i ) - ' a ' ] ++ ; } boolean flag = false ; for ( int i = 0 ; i < S2 . length ( ) ; i ++ ) { if ( freq [ S2 . charAt ( i ) - ' a ' ] == 0 ) { flag = true ; break ; } freq [ S2 . charAt ( i ) - ' a ' ] -- ; } if ( flag == true ) { System . out . println ( " No " ) ; return ; } int invCount1 = inversionCount ( S1 ) ; int invCount2 = inversionCount ( S2 ) ; if ( invCount1 == invCount2 || ( invCount1 & 1 ) == ( invCount2 & 1 ) || haveRepeated ( S1 , S2 ) ) { System . out . println ( " Yes " ) ; } else System . out . println ( " No " ) ; } public static void main ( String [ ] args ) { String S1 = " abbca " , S2 = " acabb " ; checkToMakeEqual ( S1 , S2 ) ; } }