Do you think IIT Guwahati certified course can help you in your career?
Introduction
Do you remember playing with Lego blocks as a child? You had a limited set of blocks, but with a bit of imagination and innovation, you could build almost anything you wanted. Forming a string using repeated insertions of another string is quite similar to that. This article will dive into a fun and creative problem, "Check If String S1 Can Be Formed Using Repeated Insertions Of Another String S2,"and discover how to solve it with minimum time and space complexity.
So whether you're a Lego fan or a curious coder, join us in building a solution to this fascinating problem together.
Problem Statement
We have two strings as input, S1 and S2 (consisting only of unique characters). We must determine whether the string S1 can be formed by repeated insertions of another string S2 into an empty string.
Sample Examples
Input 1
S1: "ccbdbd"
S2: "cbd"
Output 1
True
Reason
We will first add S2 to an empty string. We now have "cbd." We will again add S2 after the 'c' character, i.e., after the 0th index. Now, we have "ccbdbd," which is the same as S1 and is formed by repeated insertions of String S2 into an empty string.
Let's take another example.
Input 2
S1: "abcdefg"
S2: "ab"
Output 2
False
Reason
No matter how many times we insert S2 into the empty string, we can never get to the string S1.
Stack Approach
We will follow the stack approach to solve this problem. We will iterate through the S1 and push each character onto a stack. If the current character of S1 is equal to the last character of S2, we will pop characters from the stack and compare them to the string S2. If they are not the same or the stack becomes empty before completing the traversal of S2, we will return false. Otherwise, we return true.
Now let us look at the algorithm for the same.
Algorithm
We will use the following algorithm to code the approach mentioned above.
Set len1 to the length of S1 and len2 to the length of S2.
Create an empty stack to store the characters.
Iterate through each character in S1:
Push the current character onto the stack.
If the last character of S2 matches the current character in S1:
Set "idx" to len2 - 1, the index of the last character in S2.
Pop characters from the stack until S2 is formed in reverse order.
If the characters in S2 are not found in reverse order, return False.
If the stack is not empty, return False since repeated insertions of S2 cannot form S1.
Otherwise, return True.
Let's look at the dry run to visualize the algorithm.
Dry Run
Consider the following dry run for the above-stated algorithm.
Iteration 1:
Iteration 2:
Iteration 3:
Iteration 4:
Iteration 5:
Iteration 6:
Now that we know how our algorithm works let's look at its implementation in C++, Java, and Python.
Implementation
The implementation in C++ is as follows.
Implementation in C++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int isFormedFromString(string S1, string S2) {
// Store the size of the string
int len1 = S1.length();
int len2 = S2.length();
// Maintain a stack for characters
stack < char > charStack;
// Iterate through the string
for (int i = 0; i < len1; i++) {
charStack.push(S1[i]);
/*
If the last character of S2 and current
character is the same; then we will pop
from the stack until S2 is formed.
*/
if (S1[i] == S2[len2 - 1]) {
int idx = len2 - 1;
// Pop the characters till S2 is formed
while (idx >= 0) {
if (charStack.empty()) {
return 0;
}
char current = charStack.top();
charStack.pop();
if (current != S2[idx]) {
return 0;
}
idx--;
}
}
}
// Check if the stack is not empty.
return charStack.empty();
}
int main() {
string S1 = "ccbdbd";
string S2 = "cbd";
if (isFormedFromString(S1, S2)) {
cout << "S1 can be formed from S2" << endl;
} else {
cout << "S1 cannot be formed from S2" << endl;
}
return 0;
}
Output
The implementation in Java is as follows.
Implementation in Java
import java.util.Stack;
public class Main {
public static boolean isFormedFromString(String S1, String S2) {
// Store the size of the string
int len1 = S1.length();
int len2 = S2.length();
// Maintain a stack for characters
Stack < Character > charStack = new Stack < > ();
// Iterate through the string
for (int i = 0; i < len1; i++) {
charStack.push(S1.charAt(i));
/*
If the last character of S2 and current
Character is the same; then we will pop
from the stack until S2 is formed.
*/
if (S1.charAt(i) == S2.charAt(len2 - 1)) {
int idx = len2 - 1;
// Pop the characters till S2 is formed
while (idx >= 0) {
if (charStack.empty()) {
return false;
}
char current = charStack.pop();
if (current != S2.charAt(idx)) {
return false;
}
idx--;
}
}
}
// Check if the stack is not empty.
return charStack.empty();
}
public static void main(String[] args) {
String S1 = "ccbdbd";
String S2 = "cbd";
if (isFormedFromString(S1, S2)) {
System.out.println("S1 can be formed from S2");
} else {
System.out.println("S1 cannot be formed from S2");
}
}
}
Output
The implementation in Python is as follows.
Implementation in Python
def is_formed_from_string(S1, S2):
# Store the size of the string
len1 = len(S1)
len2 = len(S2)
# Maintain a stack for characters
char_stack = []
# Iterate through the string
for i in range(len1):
char_stack.append(S1[i])
"""
If the last character of S2 and current
Character is the same; then we will pop
from the stack until S2 is formed.
"""
if S1[i] == S2[len2 - 1]:
idx = len2 - 1
# Pop the characters till S2 is formed
while idx >= 0:
if not char_stack:
return False
current = char_stack.pop()
if current != S2[idx]:
return False
idx -= 1
# Check if the stack is not empty.
return not char_stack
if __name__ == "__main__":
S1 = "ccbdbd"
S2 = "cbd"
if is_formed_from_string(S1, S2):
print("S1 can be formed from S2")
else:
print("S1 cannot be formed from S2")
Output
Complexity Analysis
The following are the time and space complexity of this code.
Time Complexity
O(N) where N is the length of string s1. In the worst case we are pushing and popping all the characters of string s1.
Space Complexity
O(X) is the space complexity of this code. Here, X is the length of the input string S1.
Reason: This is because we use a stack to keep track of the characters in the string S1 as we iterate through it. In the worst case, the stack can potentially store all X characters. For example, when S1 does not contain any characters that match the last character in the string S2.
In addition to the stack, we also store the sizes of the strings S1 and S2 in variables X and Y, respectively, which take up constant space. We also use a few other constant-sized variables, such as the loop variable i and the character variable c.
As a result, the algorithm's overall space complexity is O(X).
Let us now address some of the frequently asked questions.
Frequently Asked Questions
Which property of a stack helped us solve this problem?
The stack's Last In First Out (L.I.F.O.) property helped us solve this question.
What if one of the input strings is empty?
If either string S1 or string S2 is empty, the algorithm will return false, as an empty string cannot be formed by repeatedly inserting another string into it.
Can we solve this problem through dynamic programming?
No, we cannot use dynamic programming to solve this problem as there is no subproblem structure we can use to build the solution for the original problem.
What is time complexity?
The amount of time an algorithm or code takes to execute each instruction is known as its time complexity.
What is space complexity?
The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity."
Conclusion
In this blog, we have covered the following things to check if string S1 can be formed using repeated insertions of another string S2. We discussed the stack-based approach to solving this problem.
You can follow these links for more such problems.
27+ registered 
