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

Nishant Rana
Last Updated: May 13, 2022

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.

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 to the stack
        st.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(M - 1)) {

            // Index of last character of the string S2
            int idx = M - 1;

            // Pop the characters till S2 is formed
            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.isEmpty()) {
        return false;
    }
    else {
        return true;
    }
}

 

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.





 

Was this article helpful ?
1 upvote