Check if string S1 can be formed using repeated insertions of another string S2 | Java program 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
import java . io . * ; import java . util . * ; class GFG { static boolean validInsertionstring ( String S1 , String S2 ) { int N = S1 . length ( ) ; int M = S2 . length ( ) ; Stack < Character > st = new Stack < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { st . push ( S1 . charAt ( i ) ) ; if ( S1 . charAt ( i ) == S2 . charAt ( M - 1 ) ) { int idx = M - 1 ; while ( idx >= 0 ) { if ( st . size ( ) == 0 ) { return false ; } char c = st . peek ( ) ; st . pop ( ) ; if ( c != S2 . charAt ( idx ) ) { return false ; } idx -- ; } } } if ( st . size ( ) > 0 ) { return false ; } else { return true ; } } public static void main ( String [ ] args ) { String S1 = " aabb " ; String S2 = " ab " ; if ( validInsertionstring ( S1 , S2 ) == true ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }