Given two strings S1 and S2 consisting of unique characters, the task is to check S1 can be formed by repeated insertions of string S2.
Input: S1 = “aabb”, S2 = “ab”
Output: Yes
Explanation: the mentioned string can be obtained after series of moves:
- Insert string “ab” in an empty string. Current string will be “ab“
- insert “ab” after “a”. The final string will be “aabb”
Input: S1 = “ababcd”, S2 = “abc”
Output: No
Explanation: It is not possible to obtain above string with any series of moves.
Approach: Given problem can be solved using stack data structure. The idea is to insert the characters of S1 into the stack till the last character of S2 is found. Then pop the characters of length(S2) from Stack and compare with S2. If not the same, stop and return false. Else repeat the process till S1 becomes empty.
Below are the steps for the above approach:
- First, check the below cases and return false if found true:
- The count of unique characters in S1 must be the same as S2
- The length of string S1 must be a multiple of S2
- Maintain a stack for all the characters
- Iterate through the string S1 and push characters in a stack
- If the current character is the last character of the string S2 then match all the characters to the left in the stack
- If for any position the stack is empty or the character doesn’t matches then return False
- After the complete iteration on the string check if the stack is empty. If the stack is not empty then return false else return true
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to check a valid insertion bool validInsertionstring(string S1, string S2) { // Store the size of string int N = S1.length(); int M = S2.length(); // Maintain a stack for characters stack< char > st; // Iterate through the string for ( int i = 0; i < N; i++) { // push the current character // on top of the stack st.push(S1[i]); // If the current character is the // last character of string S2 then // pop characters until S2 is not formed if (S1[i] == S2[M - 1]) { // index of last character of the string S2 int idx = M - 1; // pop characters till 0-th index while (idx >= 0) { if (st.empty()) { return false ; } char c = st.top(); st.pop(); if (c != S2[idx]) { return false ; } idx--; } } } // Check if stack in non-empty if (!st.empty()) { return false ; } else { return true ; } } // Driver Code int main() { string S1 = "aabb" ; string S2 = "ab" ; validInsertionstring(S1, S2) ? cout << "Yes\n" : cout << "No\n" ; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to check a valid insertion static boolean validInsertionstring(String S1, String S2) { // Store the size of string int N = S1.length(); int M = S2.length(); // Maintain a stack for characters Stack<Character> st = new Stack<>(); // Iterate through the string for ( int i = 0 ; i < N; i++) { // push the current character // on top of the stack st.push(S1.charAt(i)); // If the current character is the // last character of string S2 then // pop characters until S2 is not formed if (S1.charAt(i) == S2.charAt(M - 1 )) { // index of last character of the string S2 int idx = M - 1 ; // pop characters till 0-th index while (idx >= 0 ) { if (st.size() == 0 ) { return false ; } char c = st.peek(); st.pop(); if (c != S2.charAt(idx)) { return false ; } idx--; } } } // Check if stack in non-empty if (st.size() > 0 ) { return false ; } else { return true ; } } // Driver code 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" ); } } // This code is contributed by Potta Lokesh |
Python3
# Python3 implementation for the above approach # Function to check a valid insertion def validInsertionstring(S1, S2): # Store the size of string N = len (S1) M = len (S2) # Maintain a stack for characters st = [] # Iterate through the string for i in range (N): # push the current character # on top of the stack st.append(S1[i]) # If the current character is the # last character of string S2 then # pop characters until S2 is not formed if (S1[i] = = S2[M - 1 ]): # index of last character of the string S2 idx = M - 1 # pop characters till 0-th index while (idx > = 0 ): if ( len (st) = = 0 ): return False c = st[ - 1 ] st.pop() if (c ! = S2[idx]): return False idx - = 1 # Check if stack in non-empty if ( len (st) ! = 0 ): return False else : return True S1 = "aabb" S2 = "ab" if validInsertionstring(S1, S2): print ( "Yes" ) else : print ( "No" ) # This code is contributed by divyeshrabadiya07. |
C#
// C# implementation for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check a valid insertion static bool validInsertionstring( string S1, string S2) { // Store the size of string int N = S1.Length; int M = S2.Length; // Maintain a stack for characters Stack< char > st = new Stack< char >(); // Iterate through the string for ( int i = 0; i < N; i++) { // push the current character // on top of the stack st.Push(S1[i]); // If the current character is the // last character of string S2 then // pop characters until S2 is not formed if (S1[i] == S2[M - 1]) { // index of last character of the string S2 int idx = M - 1; // pop characters till 0-th index while (idx >= 0) { if (st.Count==0) { return false ; } char c = st.Peek(); st.Pop(); if (c != S2[idx]) { return false ; } idx--; } } } // Check if stack in non-empty if (st.Count > 0) { return false ; } else { return true ; } } // Driver Code public static void Main() { string S1 = "aabb" ; string S2 = "ab" ; if (validInsertionstring(S1, S2)== true ) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // Javascript implementation for the above approach // Function to check a valid insertion function validInsertionstring(S1, S2) { // Store the size of string let N = S1.length; let M = S2.length; // Maintain a stack for characters let st = []; // Iterate through the string for (let i = 0; i < N; i++) { // push the current character // on top of the stack st.push(S1[i]); // If the current character is the // last character of string S2 then // pop characters until S2 is not formed if (S1[i] == S2[M - 1]) { // index of last character of the string S2 let idx = M - 1; // pop characters till 0-th index while (idx >= 0) { if (st.length == 0) { return false ; } let c = st[st.length - 1]; st.pop(); if (c != S2[idx]) { return false ; } idx--; } } } // Check if stack in non-empty if (st.length != 0) { return false ; } else { return true ; } } let S1 = "aabb" ; let S2 = "ab" ; validInsertionstring(S1, S2) ? document.write( "Yes" ) : document.write( "No" ); // This code is contributed by suresh07. </script> |
Yes
Time Complexity: O(N*M)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!