Convert given string to another by minimum replacements of subsequences by its smallest character | C ++ program for the above approach ; Function to return the minimum number of operation ; Storing data ; Initialize both arrays ; Stores the index of character ; Filling str1array , convChar and hashmap convertMap . ; Not possible to convert ; Calculate result Initializing return values ; Iterating the character from the end ; Increment the number of operations ; Not possible to convert ; to check whether the final element has been added in set S or not . ; Check if v1 [ j ] is present in hashmap or not ; Already converted then then continue ; Not possible to convert ; Print the result ; Driver Code ; Given strings ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void transformString ( string str1 , string str2 ) { int N = str1 . length ( ) ; vector < int > convChar [ 26 ] ; vector < int > str1array [ 26 ] ; for ( int i = 0 ; i < 26 ; i ++ ) { vector < int > v ; convChar [ i ] = v ; str1array [ i ] = v ; } map < int , char > convertMap ; for ( int i = 0 ; i < N ; i ++ ) { str1array [ str1 [ i ] - ' a ' ] . push_back ( i ) ; } for ( int i = 0 ; i < N ; i ++ ) { if ( str1 [ i ] < str2 [ i ] ) { cout << -1 << endl ; return ; } else if ( str1 [ i ] == str2 [ i ] ) continue ; else { convChar [ str2 [ i ] - ' a ' ] . push_back ( i ) ; convertMap [ i ] = str2 [ i ] ; } } int ret = 0 ; vector < vector < int > > retv ; for ( int i = 25 ; i >= 0 ; i -- ) { vector < int > v = convChar [ i ] ; if ( v . size ( ) == 0 ) continue ; ret ++ ; vector < int > v1 = str1array [ i ] ; if ( v1 . size ( ) == 0 ) { cout << -1 << endl ; return ; } bool isScompleted = false ; for ( int j = 0 ; j < v1 . size ( ) ; j ++ ) { if ( convertMap . find ( v1 [ j ] ) != convertMap . end ( ) ) { char a = convertMap [ v1 [ j ] ] ; if ( a > i + ' a ' ) continue ; else { v . push_back ( v1 [ j ] ) ; isScompleted = true ; retv . push_back ( v ) ; break ; } } else { v . push_back ( v1 [ j ] ) ; isScompleted = true ; retv . push_back ( v ) ; break ; } } if ( ! isScompleted ) { cout << -1 << endl ; return ; } } cout << ret << endl ; } int main ( ) { string A = " abcab " ; string B = " aabab " ; transformString ( A , B ) ; return 0 ; }