Minimum number of subsequences required to convert one string to another using Greedy Algorithm | Java implementation for minimum number of subsequences required to convert one String to another ; Function to find the minimum number of subsequences required to convert one String to another S2 == A and S1 == B ; At least 1 subsequence is required Even in best case , when A is same as B ; size of B ; size of A ; Create an 2D array next [ ] [ ] of size 26 * sizeOfB to store the next occurrence of a character ( ' a ' to ' z ' ) as an index [ 0 , sizeOfA - 1 ] ; Array Initialization with infinite ; Loop to Store the values of index ; If the value of next [ i ] [ j ] is infinite then update it with next [ i ] [ j + 1 ] ; Greedy algorithm to obtain the maximum possible subsequence of B to cover the remaining String of A using next subsequence ; Loop to iterate over the String A ; Condition to check if the character is not present in the String B ; Condition to check if there is an element in B matching with character A [ i ] on or next to B [ pos ] given by next [ A [ i ] - ' a ' ] [ pos ] ; Condition to check if reached at the end of B or no such element exists on or next to A [ pos ] , thus increment number by one and reinitialise pos to zero ; Driver Code
class GFG { static int findMinimumSubsequences ( String A , String B ) { int numberOfSubsequences = 1 ; int sizeOfB = B . length ( ) ; int sizeOfA = A . length ( ) ; int inf = 1000000 ; int [ ] [ ] next = new int [ 26 ] [ sizeOfB ] ; for ( int i = 0 ; i < 26 ; i ++ ) { for ( int j = 0 ; j < sizeOfB ; j ++ ) { next [ i ] [ j ] = inf ; } } for ( int i = 0 ; i < sizeOfB ; i ++ ) { next [ B . charAt ( i ) - ' a ' ] [ i ] = i ; } for ( int i = 0 ; i < 26 ; i ++ ) { for ( int j = sizeOfB - 2 ; j >= 0 ; j -- ) { if ( next [ i ] [ j ] == inf ) { next [ i ] [ j ] = next [ i ] [ j + 1 ] ; } } } int pos = 0 ; int i = 0 ; while ( i < sizeOfA ) { if ( pos == 0 && next [ A . charAt ( i ) - ' a ' ] [ pos ] == inf ) { numberOfSubsequences = - 1 ; break ; } else if ( pos < sizeOfB && next [ A . charAt ( i ) - ' a ' ] [ pos ] < inf ) { int nextIndex = next [ A . charAt ( i ) - ' a ' ] [ pos ] + 1 ; pos = nextIndex ; i ++ ; } else { numberOfSubsequences ++ ; pos = 0 ; } } return numberOfSubsequences ; } public static void main ( String [ ] args ) { String A = " aacbe " ; String B = " aceab " ; System . out . print ( findMinimumSubsequences ( A , B ) ) ; } }