Check if string S2 can be obtained by appending subsequences of string S1 | Python3 Program to implement the above approach ; Function for finding minimum number of operations ; Stores the length of strings ; Stores frequency of characters in string s ; Update frequencies of character in s ; Traverse string s1 ; If any character in s1 is not present in s ; Stores the indices of each character in s ; Traverse string s ; Store indices of characters ; Stores index of last appended character ; Traverse string s1 ; Find the index of next character that can be appended ; Check if the current character be included in the current subsequence ; Otherwise ; Start a new subsequence ; Update index of last character appended ; Driver Code ; If S2 cannot be obtained from subsequences of S1 ; Otherwise
from bisect import bisect , bisect_left , bisect_right NEW_LINE def findMinimumOperations ( s , s1 ) : NEW_LINE INDENT n = len ( s ) NEW_LINE m = len ( s1 ) NEW_LINE frequency = [ 0 ] * 26 NEW_LINE for i in range ( n ) : NEW_LINE INDENT frequency [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT for i in range ( m ) : NEW_LINE INDENT if ( frequency [ ord ( s1 [ i ] ) - ord ( ' a ' ) ] == 0 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT indices = [ [ ] for i in range ( 26 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT indices [ ord ( s [ i ] ) - ord ( ' a ' ) ] . append ( i ) NEW_LINE DEDENT ans = 2 NEW_LINE last = len ( indices [ ord ( s1 [ 0 ] ) - ord ( ' a ' ) ] ) - 1 NEW_LINE for i in range ( 1 , m ) : NEW_LINE INDENT ch = ord ( s1 [ i ] ) - ord ( ' a ' ) NEW_LINE it = bisect_right ( indices [ ch ] , last ) NEW_LINE if ( it != len ( indices [ ch ] ) ) : NEW_LINE INDENT last = it NEW_LINE DEDENT else : NEW_LINE INDENT ans += 1 NEW_LINE last = len ( indices [ ch ] ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S1 = " acebcd " NEW_LINE S2 = " acbcde " NEW_LINE ans = findMinimumOperations ( S1 , S2 ) NEW_LINE if ( ans == - 1 ) : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " YES " ) NEW_LINE print ( ans ) NEW_LINE DEDENT DEDENT