Minimum number of subsequences required to convert one string to another using Greedy Algorithm | Function to find the minimum number of subsequences required to convert one 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 ] ; 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 of A using next subsequence ; Loop to iterate over the A ; Condition to check if the character is not present in the 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
def findMinimumSubsequences ( A , B ) : NEW_LINE INDENT numberOfSubsequences = 1 NEW_LINE sizeOfB = len ( B ) NEW_LINE sizeOfA = len ( A ) NEW_LINE inf = 1000000 NEW_LINE next = [ [ inf for i in range ( sizeOfB ) ] for i in range ( 26 ) ] NEW_LINE for i in range ( sizeOfB ) : NEW_LINE INDENT next [ ord ( B [ i ] ) - ord ( ' a ' ) ] [ i ] = i NEW_LINE DEDENT for i in range ( 26 ) : NEW_LINE INDENT for j in range ( sizeOfB - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( next [ i ] [ j ] == inf ) : NEW_LINE INDENT next [ i ] [ j ] = next [ i ] [ j + 1 ] NEW_LINE DEDENT DEDENT DEDENT pos = 0 NEW_LINE i = 0 NEW_LINE while ( i < sizeOfA ) : NEW_LINE INDENT if ( pos == 0 and next [ ord ( A [ i ] ) - ord ( ' a ' ) ] [ pos ] == inf ) : NEW_LINE INDENT numberOfSubsequences = - 1 NEW_LINE break NEW_LINE DEDENT elif ( pos < sizeOfB and next [ ord ( A [ i ] ) - ord ( ' a ' ) ] [ pos ] < inf ) : NEW_LINE INDENT nextIndex = next [ ord ( A [ i ] ) - ord ( ' a ' ) ] [ pos ] + 1 NEW_LINE pos = nextIndex NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT numberOfSubsequences += 1 NEW_LINE pos = 0 NEW_LINE DEDENT DEDENT return numberOfSubsequences NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = " aacbe " NEW_LINE B = " aceab " NEW_LINE print ( findMinimumSubsequences ( A , B ) ) NEW_LINE DEDENT