text: Check if a string can be transformed to another by sorting substrings | C ++ Program to implement the above approach ; Function to check if str1 can be transformed to t by sorting substrings ; Occur [ i ] stores the indices of char ( ' a ' + i ) in string s ; idx [ i ] stores the next available index of char ( ' a ' + i ) in occur [ i ] ; If this char is not available anymore ; Conversion not possible ; If one of the smaller characters is available and occurs before ; Conversion not possible ; Print the answer ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void canTransform ( string & s , string & t ) { int n = s . length ( ) ; vector < int > occur [ 26 ] ; for ( int x = 0 ; x < n ; x ++ ) { char ch = s [ x ] - ' a ' ; occur [ ch ] . push_back ( x ) ; } vector < int > idx ( 26 , 0 ) ; bool poss = true ; for ( int x = 0 ; x < n ; x ++ ) { char ch = t [ x ] - ' a ' ; if ( idx [ ch ] >= occur [ ch ] . size ( ) ) { poss = false ; break ; } for ( int small = 0 ; small < ch ; small ++ ) { if ( idx [ small ] < occur [ small ] . size ( ) && occur [ small ] [ idx [ small ] ] < occur [ ch ] [ idx [ ch ] ] ) { poss = false ; break ; } } idx [ ch ] ++ ; } if ( poss ) { cout << " Yes " << endl ; } else { cout << " No " << endl ; } } int main ( ) { string s , t ; s = " hdecb " ; t = " cdheb " ; canTransform ( s , t ) ; return 0 ; }