Check if a string is a subsequence of another string using stack

Riya
Last Updated: May 13, 2022

Introduction-  

This article will discuss how to check if a string is a subsequence of another string using the stack data structure. Before jumping into the implementation details and its C++ code, you need to know about the stack data structure. 
Now, let's understand the problem.  
In this problem, we will be given two strings, "s1" and "s2," and we have to check whether "s1" is a subsequence of "s2" or not. Before moving to the approach to solve the problem, let's understand what a "subsequence" is. 

A string "s1" can be called a subsequence of another string "s2" if "s1" can be obtained after deleting zero, one or more characters from "s2" without disturbing the relative order of the remaining characters.

Let's take an example to understand the problem: 
Assume s1 = “oig”                           and s2 = ”coding”

We can see that if we delete the characters at positions 0, 2, 4 and keep the remaining characters in the same relative position, we will get "oig". So, "s1" is the subsequence of "s2". 
Let's take a look at another example: 
Assume s1 = “axy”            and s2 =  “yadxcp” 
You may have figured out that axy cannot be obtained from s2. Hence s1 is not a subsequence of s1 
In the next section, we will discuss an approach to check if a string is a subsequence of another string using the stack data structure.

Solution Approach

We have to check if a string is a subsequence of another string. The approach is first to create a stack and push all the characters of "s2" from beginning to end. Now, we will check for the characters of "s1" one by one. We will start from the last character of "s1" and continue checking until we find all the characters of "s1" or the stack has no character. We are starting from the last character of "s2" because the stack will have the last inserted element of "s2" at the top as it is a "Last In First Out" type of data structure. If we can find all the characters of "s1" in the stack, which has the characters of "s2",  then we can say that "s1" is a subsequence of "s2".

Let's understand this algorithm using the example given in the previous section. 
Here, 
s1 = “oig” and s2 = “coding” 
We have to check whether the "s1" is a subsequence of "s2".

  Fig: Dry run of an example for the following algorithm to check if a string is a subsequence of another string using stack data structure.

 Algorithm -

Step 1. Create a function "checkForSubsequence()" to [check if a string is a subsequence of another string using stack. It will take two inputs "s1" and "s2" and check if "s1" is a subsequence of "s2" then return boolean value "true", else return boolean "false". Step 2. Insert all the characters of "s2" in the stack, starting from the first to the last.  
Step 3.  Create a variable "currentIndex", which will store the current character index of "s1". Initialize the "currentIndex" as the index of the last character of "s1". Next, create a "while loop" to search for each character of "s1," starting from its last character to its first character. Stop the "while loop" when "currentIndex" becomes less than zero, which means we have found all the characters of "s1" or when the stack becomes empty which means we have completely searched in "s2".  
Step 4. Inside the "while loop", compare the top element of the stack with the current character of "s1". The following two cases will arise:

  1. The current character of "s1" and the top element of the stack will be equal: In this case, pop the top element and decrease "currentIndex" by 1.
  2. The current character of "s1" and the top element of the stack will not be equal: In this case, pop the top element and don't decrease "currentIndex" as we have not find the current character of "s1".

Step 5. Finally, after the completion of "while loop", check the value of "currentIndex". If its value less than zero return "true", else return "false".

C++ code:

#include <bits/stdc++.h>
using namespace std;
// Function to check if a string is a subsequence of another string
bool checkforSubsequence(string s1, string s2)
{
   // We have to check if s1 is a subsequence of s2
   
   // Declaring a stack to insert the characters of the second string i.e. s2
   stack<char> s;

   // Inserting all the characters of s2 into the stack
   for (int i = 0; i < s2.size(); i++) {
       s.push(s2[i]);
   }

   // Initializing a variable to store the index of last character of s1
   int currentIndex = s1.size()-1;
   
   /* 
      Stop the while loop if either we have found all
      the elements of "s1" and "currentIndex" 
      becomes less than zero or the stack become empty
   */
   while(currentIndex>=0 || !s.empty())
     {
      if(s.top() == s1[currentIndex]) {
       s.pop();
       currentIndex--;
      }
      else {
       s.pop();
      }
     }
    
   
   /*
      If we have found all the characters of "s1", 
      then currentIndex will have become less than zero
   */
   if(currentIndex < 0) return true;
   else return false;
  
}

int main()
{
   string s1 = "oig";
   string s2 = "coding";

   // Call the function to check is a string is a subsequence of another string
   bool isSubsequence = checkforSubsequence(s1, s2);

   if(isSubsequence) {
    cout<<"Yes, \""<<s1<<"\" is a subsequence of \""<<s2<<"\""<<endl;
   }
   else {
    cout<<"No, \""<<s1<<"\" is not a subsequence of \""<<s2<<"\""<<endl;
   }
   return 0;
}

The output for the above program is 
Yes, "oig" is a subsequence of "coding"

Java Code

import java.util.Stack;
class Main {
// Function to check if a string is a subsequence of another string
static boolean checkForSubsequence(String s1, String s2)
{
// Declaring a stack to insert the characters of the second string i.e. s2
Stack<Character> stack = new Stack<Character>();

// Inserting all the characters of s2 into the stack
for(int i = 0; i < s1.length(); i++)
{
stack.push(s1.charAt(i));
}
for(int i = (int)s2.length() - 1; i >= 0; i--)
{
if(stack.isEmpty()){
return true;
}

if(s2.charAt(i) == stack.peek()){
stack.pop();
}
}

if(stack.isEmpty()){
return true;
}
return false;


}
public static void main(String args[]) {
String s1 = "KOTA";
             String s2 = "KOTAYAM";


if(checkForSubsequence(s1, s2)){
System.out.println("Yes " + s1 + " is a subsequence of " + s2);
}
else{
System.out.println("No " + s1 + " is not a subsequence of "  + s2);
      }
}
}

The output for the above program is

Yes KOTA is a subsequence of KOTAYAM

Python Code

def checkforSubsequence(s1, s2):

	# Declare a stack
	stack = []
	# Push the characters of target into the stack
	for i in range(len(s1)):
		stack.append(s1[i])

	# Traverse the string S in reverse
	for i in range(len(s2) - 1, -1, -1):
		# If the stack is empty
		if (len(stack) == 0):
			print(s1 + " is a subsequence of " + s2);
			return

		# If S[i] is same as the top of the stack
		if (s2[i] == stack[-1]):
		# Pop the top of stack
			stack.pop()


	# Stack s is empty
	if (len(stack) == 0):
		print(s1 + " is a subsequence of " + s2);


	else:
		print("No")


# Driver Code
if __name__ == "__main__":


s1 = "KOTA"
s2 = "KOTAYAM"


checkforSubsequence(s1, s2)

The output for the above program is 
Yes KOTA is a subsequence of KOTAYAM

Algorithm Complexity: 

Time Complexity: O(N) 
In the function "checkForSubsequence()" to check if a string is a subsequence of another string using stack, we have created the "while loop" which will maximum have 'N' number of iterations where 'N' is the length of the string in which we have to search for the subsequence. So, time complexity will be O(N).

Space Complexity: O(N)  
In the function "checkForSubsequence()" to check if a string is a subsequence of another string using stack, we have created a stack to store all the characters of the string in which we have to search for the subsequence. So, space complexity will be O(N), where 'N' is the length of the string in which we have to search for the subsequence.

Frequently asked questions-

  1. What is a stack? 
    A stack is a linear data structure which follows the “Last In First Out” order. Elements are pushed and popped from the sem end of a stack. So, the element pushed in the last will be at top and will be popped first.
  2. How can you check if a string is a subsequence of another string?
    A stack can be used in the following manner: Firstly push all the characters of "s2" from beginning to end. Now, we will check for the characters of "s1" one by one, starting from the last character of "s1" and continue checking until we find all the characters of "s1" or the stack has no character.
  3. How does stack help in checking if string is a subsequence of another string?
    We are using a stack to store all the characters of the string in which we have to search for the subsequence. Because of the stack, the characters are in the fixed relative order even after popping, so we can easily search for the subsequence as for being subsequence relative ordering of characters should be same.

Key takeaways-

This article discussed an important interview question, checking if a string is a subsequence of another or not with examples, code and complexity analysis. It's the right time to solve related questions on Codestudio, the more you practise, the more you grow  
If you think that this blog helped you, then share it with your friends!. Preparing for placements, internships and not getting the right resource for your journey to product based companies, we have got you covered, Refer to our DSA C++ course ang get ready for your placements with us. 
Until then, All the best for your future endeavours, and Keep Coding.

Was this article helpful ?
1 upvote