Check if string S1 can be formed using repeated insertions of another string S2 | Function to check a valid insertion ; Store the size of string ; Maintain a stack for characters ; Iterate through the string ; push the current character on top of the stack ; If the current character is the last character of string S2 then pop characters until S2 is not formed ; index of last character of the string S2 ; pop characters till 0 - th index ; Check if stack in non - empty ; Driver Code
def validInsertionstring ( S1 , S2 ) : NEW_LINE INDENT N = len ( S1 ) NEW_LINE M = len ( S2 ) NEW_LINE st = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT st . append ( S1 [ i ] ) NEW_LINE if ( S1 [ i ] == S2 [ M - 1 ] ) : NEW_LINE INDENT idx = M - 1 NEW_LINE while ( idx >= 0 ) : NEW_LINE INDENT if ( len ( st ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT c = st [ - 1 ] NEW_LINE st . pop ( ) NEW_LINE if ( c != S2 [ idx ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT idx -= 1 NEW_LINE DEDENT DEDENT DEDENT if ( len ( st ) != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT S1 = " aabb " NEW_LINE S2 = " ab " NEW_LINE if validInsertionstring ( S1 , S2 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT