Convert given string to another by minimum replacements of subsequences by its smallest character | Java 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
import java . util . * ; import java . lang . * ; class GFG { static void transformString ( String str1 , String str2 ) { int N = str1 . length ( ) ; ArrayList < ArrayList < Integer > > convChar = new ArrayList < > ( ) ; ArrayList < ArrayList < Integer > > str1array = new ArrayList < > ( ) ; for ( int i = 0 ; i < 26 ; i ++ ) { convChar . add ( new ArrayList < > ( ) ) ; str1array . add ( new ArrayList < > ( ) ) ; } Map < Integer , Character > convertMap = new HashMap < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { str1array . get ( str1 . charAt ( i ) - ' a ' ) . add ( i ) ; } for ( int i = 0 ; i < N ; i ++ ) { if ( str1 . charAt ( i ) < str2 . charAt ( i ) ) { System . out . println ( - 1 ) ; return ; } else if ( str1 . charAt ( i ) == str2 . charAt ( i ) ) continue ; else { convChar . get ( str2 . charAt ( i ) - ' a ' ) . add ( i ) ; convertMap . put ( i , str2 . charAt ( i ) ) ; } } int ret = 0 ; ArrayList < ArrayList < Integer > > retv = new ArrayList < > ( ) ; for ( int i = 25 ; i >= 0 ; i -- ) { ArrayList < Integer > v = convChar . get ( i ) ; if ( v . size ( ) == 0 ) continue ; ret ++ ; ArrayList < Integer > v1 = str1array . get ( i ) ; if ( v1 . size ( ) == 0 ) { System . out . println ( - 1 ) ; return ; } boolean isScompleted = false ; for ( int j = 0 ; j < v1 . size ( ) ; j ++ ) { if ( convertMap . containsKey ( v1 . get ( j ) ) ) { char a = convertMap . get ( v1 . get ( j ) ) ; if ( a > i + ' a ' ) continue ; else { v . add ( v1 . get ( j ) ) ; isScompleted = true ; retv . add ( v ) ; break ; } } else { v . add ( v1 . get ( j ) ) ; isScompleted = true ; retv . add ( v ) ; break ; } } if ( ! isScompleted ) { System . out . println ( - 1 ) ; return ; } } System . out . println ( ret ) ; } public static void main ( String [ ] args ) { String A = " abcab " ; String B = " aabab " ; transformString ( A , B ) ; } }