# Check if string S1 can be formed using repeated insertions of another string S2

## Introduction:

We are given two strings S1 and S2(consist of only unique characters). We need to check if string S1 can be formed using repeated insertions of another string S2 to an empty String.

Input 1:

S1: “ccbdbd”

S2: “cbd”

Output 1:

True

Explanation 1:

We will first add S2 to an empty string. We have now “cbd”. We will again add S2 after ‘c’ character i.e. after the 0th index. Now, we have “ccbdbd” which is same as S1 and is formed by repeated insertions of String S2.

Input 2:

S1: “ccbdbd”

S2: “cbd”

Output 1:

True

Explanation 1:

We will first add S2 to an empty string. We have now “cbd”. We will again add S2 after ‘c’ character i.e. after the 0th index. Now, we have “ccbdbd” which is same as S1 and is formed by repeated insertions of String S2.

## Approach:

First of all, we need to check if all the characters of S1 and S2 are identical or not. If any of the characters is not the same, we will directly return false.

We will now initialize a Stack.

We will follow the following steps:-

1. We will iterate the S1 String.
2. If the current character is the same as the last character of the S2 String we will check if all the characters on the left of S2 are the same in the Stack or not.
3. If during the check Stack gets empty or the character in the Stack is not the same as the character in S2 then we will return false.
4. After the iteration, we need to check if the Stack is empty or not. If the stack is empty we will return true else false.

Refer to the below implementation of the above approach.

Time Complexity: The time complexity of the above approach is O(N * M) (where ‘N’ is the length of the String S1 and ‘M’ is the length of the String S2) because we are iterating the String S1 once and in the worst case for each iteration we will iterate the String S2.

Space Complexity: The space complexity for the above approach is O(N) because we are maintaining a Stack that will store all the characters of the String in the worst case.

## FAQs:

1. What are the Time and Space complexity of the approach used to Check if string S1 can be formed using repeated insertions of another string S2?
• Time Complexity: The time complexity of the above approach is O(N * M) (where N is the length of the String S1 and M is the length of the String S2) because we are iterating the String S1 once and in the worst case for each iteration we will iterate the String S2.
• Space Complexity: The space complexity for the above approach is O(N) because we are maintaining a Stack that will store all the characters of the String in the worst case.
2. Which property of stack helped us to Check if string S1 can be formed using repeated insertions of another string S2?
• The Last In First Out(L.I.F.O.) property of the stack helped us to solve this question.

## Key Takeaways:

In this blog, we have covered the following things to check if string S1 can be formed using repeated insertions of another string S2:

1. We first discussed the Stack approach to check if string S1 can be formed using repeated insertions of another string S2.
2. Then we discussed the time and space complexity of the approach used to check if string S1 can be formed using repeated insertions of another string S2.

If you want to learn more about Stack and want to practice some questions which require you to take your basic knowledge on Stack a notch higher, then you can visit our Guided Path for Stack. To practice this problem, you can visit Practice Problem.

Until then, All the best for your future endeavors, and Keep Coding.  