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
function validInsertionstring ( S1 , S2 ) { let N = S1 . length ; let M = S2 . length ; let st = [ ] ; for ( let i = 0 ; i < N ; i ++ ) { st . push ( S1 [ i ] ) ; if ( S1 [ i ] == S2 [ M - 1 ] ) { let idx = M - 1 ; while ( idx >= 0 ) { if ( st . length == 0 ) { return false ; } let c = st [ st . length - 1 ] ; st . pop ( ) ; if ( c != S2 [ idx ] ) { return false ; } idx -- ; } } } if ( st . length != 0 ) { return false ; } else { return true ; } } let S1 = " " ; let S2 = " " ; validInsertionstring ( S1 , S2 ) ? document . write ( " " ) : document . write ( " " ) ;