text: Check whether two strings can be made equal by reversing substring of equal length from both strings | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int inversionCount ( string & s ) { int freq [ 26 ] = { 0 } ; int inv = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { int temp = 0 ; for ( int j = 0 ; j < int ( s [ i ] - ' a ' ) ; j ++ ) temp += freq [ j ] ; inv += ( i - temp ) ; freq [ s [ i ] - ' a ' ] ++ ; } return inv ; } bool haveRepeated ( string & S1 , string & S2 ) { int freq [ 26 ] = { 0 } ; for ( char i : S1 ) { if ( freq [ i - ' a ' ] > 0 ) return true ; freq [ i - ' a ' ] ++ ; } for ( int i = 0 ; i < 26 ; i ++ ) freq [ i ] = 0 ; for ( char i : S2 ) { if ( freq [ i - ' a ' ] > 0 ) return true ; freq [ i - ' a ' ] ++ ; } return false ; } void checkToMakeEqual ( string S1 , string S2 ) { int freq [ 26 ] = { 0 } ; for ( int i = 0 ; i < S1 . length ( ) ; i ++ ) { freq [ S1 [ i ] - ' a ' ] ++ ; } bool flag = 0 ; for ( int i = 0 ; i < S2 . length ( ) ; i ++ ) { if ( freq [ S2 [ i ] - ' a ' ] == 0 ) { flag = true ; break ; } freq [ S2 [ i ] - ' a ' ] -- ; } if ( flag == true ) { cout << " No STRNEWLINE " ; return ; } int invCount1 = inversionCount ( S1 ) ; int invCount2 = inversionCount ( S2 ) ; if ( invCount1 == invCount2 || ( invCount1 & 1 ) == ( invCount2 & 1 ) || haveRepeated ( S1 , S2 ) ) { cout << " Yes STRNEWLINE " ; } else cout << " No STRNEWLINE " ; } int main ( ) { string S1 = " abbca " , S2 = " acabb " ; checkToMakeEqual ( S1 , S2 ) ; return 0 ; }