Check if a string can be transformed to another by sorting substrings | Java 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
import java . util . * ; class GFG { static void canTransform ( String s , String t ) { int n = s . length ( ) ; Vector < Integer > occur [ ] = new Vector [ 26 ] ; for ( int i = 0 ; i < occur . length ; i ++ ) occur [ i ] = new Vector < Integer > ( ) ; for ( int x = 0 ; x < n ; x ++ ) { char ch = ( char ) ( s . charAt ( x ) - ' a ' ) ; occur [ ch ] . add ( x ) ; } int [ ] idx = new int [ 26 ] ; boolean poss = true ; for ( int x = 0 ; x < n ; x ++ ) { char ch = ( char ) ( t . charAt ( 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 ] . get ( idx [ small ] ) < occur [ ch ] . get ( idx [ ch ] ) ) { poss = false ; break ; } } idx [ ch ] ++ ; } if ( poss ) { System . out . print ( " Yes " + "NEW_LINE"); } else { System . out . print ( " No " + "NEW_LINE"); } } public static void main ( String [ ] args ) { String s , t ; s = " hdecb " ; t = " cdheb " ; canTransform ( s , t ) ; } }