Minimum number of subsequences required to convert one string to another | Python3 program to find the Minimum number of subsequences required to convert one to another ; Function to find the no of subsequences ; Push the values of indexes of each character ; Find the next index available in the array ; If Character is not in A ; Check if the next index is not equal to the size of array which means there is no index greater than minIndex in the array ; Update value of minIndex with this index ; Update the value of counter and minIndex for next operation ; Driver Code
from bisect import bisect as upper_bound NEW_LINE def minSubsequnces ( A , B ) : NEW_LINE INDENT v = [ [ ] for i in range ( 26 ) ] NEW_LINE minIndex = - 1 NEW_LINE cnt = 1 NEW_LINE j = 0 NEW_LINE flag = 0 NEW_LINE for i in range ( len ( A ) ) : NEW_LINE INDENT p = ord ( A [ i ] ) - 97 NEW_LINE v [ p ] . append ( i ) NEW_LINE DEDENT while ( j < len ( B ) ) : NEW_LINE INDENT p = ord ( B [ j ] ) - 97 NEW_LINE k = upper_bound ( v [ p ] , minIndex ) NEW_LINE if ( len ( v [ p ] ) == 0 ) : NEW_LINE INDENT flag = 1 NEW_LINE break NEW_LINE DEDENT if ( k != len ( v [ p ] ) ) : NEW_LINE INDENT minIndex = v [ p ] [ k ] NEW_LINE j = j + 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt = cnt + 1 NEW_LINE minIndex = - 1 NEW_LINE DEDENT DEDENT if ( flag == 1 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return cnt NEW_LINE DEDENT A1 = " abbace " NEW_LINE B1 = " acebbaae " NEW_LINE print ( minSubsequnces ( A1 , B1 ) ) NEW_LINE