Check if string S1 can be formed using repeated insertions of another string S2 | C ++ implementation for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool validInsertionstring ( string S1 , string S2 ) { int N = S1 . length ( ) ; int M = S2 . length ( ) ; stack < char > st ; for ( int i = 0 ; i < N ; i ++ ) { st . push ( S1 [ i ] ) ; if ( S1 [ i ] == S2 [ M - 1 ] ) { int idx = M - 1 ; while ( idx >= 0 ) { if ( st . empty ( ) ) { return false ; } char c = st . top ( ) ; st . pop ( ) ; if ( c != S2 [ idx ] ) { return false ; } idx -- ; } } } if ( ! st . empty ( ) ) { return false ; } else { return true ; } } int main ( ) { string S1 = " aabb " ; string S2 = " ab " ; validInsertionstring ( S1 , S2 ) ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; }