Check if a String is a Subsequence of Another String using Stack

Approach

We will use stack to check if a string is a subsequence of another string.  Let the main string be ‘string1’ and the subsequence string is ‘string2’. We will add the characters of ‘string2’ in the stack individually. After inserting the characters in the stack, we will compare the top element in the stack with the ‘string1’ characters. 

We will start at the last index in the ‘string2’ to compare the characters because the stack will reverse the order of the ‘string2’, so we start at the last index to maintain the correct order.

If the top element in the stack is equal to the character at the current index, then we will remove the top from the stack. We will compare until the stack is empty or the size of the ‘string1’ is greater than 0. If the stack is empty, the ‘string2’ is a subsequence of the ‘string1’; else not.

Algorithm

1. Declare the string1 and string2 where string2 is the subsequent string.
    
2. Initialize the stack to store the characters from string2.
    
3. Insert the string2 characters in the stack.
    
4. Compare the top of the stack with the current index character in string1.
    
5. Repeat step 4 until the stack is empty or the current index is smaller than 0.
    
6. If the stack is empty, return true as output.
    
7. If the stack is not empty, return false.

DRY Run

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

// Function to check if a string is a subsequence of another string
bool checkforSubsequence(string string2, string string1) {

    // We have to check if string2 is a subsequence of string1

    // Declaring a stack to insert the characters of the second string i.e., string1
    stack < char > checkstack;

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

    // Initializing a variable to store the index of last character of string2
    int currentIndex = (string1.size() - 1);

    /* 
       Stop the while loop if either we have found all
       the elements of "string2" and "currentIndex" 
       becomes less than zero or the stack become empty
    */
    while (!checkstack.empty() && currentIndex >= 0) {

        if (checkstack.top() == string1[currentIndex]) {
            checkstack.pop();
        }
        currentIndex--;
    }

    /*
       If we have found all the characters of "string2", 
       then currentIndex will have become less than zero
    */
    if (checkstack.empty()) return true;
    else return false;

}

int main() {
    string string1 = "coding";
    string string2 = "oig";

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

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

You can also try this code with Online C++ Compiler

Run Code

Output

Implementation in Java

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

        // Inserting all the characters of string2 into the stack
        for (int i = 0; i < string2.length(); i++) {
            checkseq.push(string2.charAt(i));
        }

        int currentIndex = string1.length() - 1;

        // Checking the subsequence in string1
        while (!checkseq.isEmpty() && currentIndex >= 0) {
            if (string1.charAt(currentIndex) == checkseq.peek()) {
                checkseq.pop();
            }
            currentIndex--;
        }

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

    }

    // Driver code
    public static void main(String args[]) {
        String string1 = "coding";
        String string2 = "oig";

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

You can also try this code with Online Java Compiler

Run Code

Output

Implementation in Python

def checkforSubsequence(string2, string1):

	# Declare a stack
	checkseq = []

	# Push the characters of
	# target into the stack
	for i in range(len(string2)):
		checkseq.append(string2[i])
	
	currentindex = len(string1) - 1
	
	# Traverse the string1 in reverse
	while(checkseq and currentindex>=0):
		if (string1[currentindex] == checkseq[-1]):
		    
			# Pop the top of stack
			checkseq.pop()
		currentindex-=1 

	# Checking if stack is empty or not,
	if (not checkseq):
		print("Yes," + "'" + string2 + "'" + " is a subsequence of " + "'" + string1 + "'");

	else:
		print("No," + "'" + string2 + "'" + " is not a subsequence of " + "'" + string1 + "'");

# Driver Code
if __name__ == "__main__":

	string1 = "coding"
	string2 = "oig"

	checkforSubsequence(string2, string1)

You can also try this code with Online Python Compiler

Run Code

Output

Complexity Analysis

The time complexity for the above approach will be O(N + M), where ‘N’ And ‘M’ are the size of string1 and string2 respectively. We iterate over string2 to add it to stack and then iterate over string1 to check if the string2 is subsequence of string1 or not.

The space complexity will be O(M), where ‘M’ is the stack size we have used to store the characters of string2. 

Must Read Stack Operations

Frequently Asked Questions

What is a stack?

Stack is a linear data structure that we can use to store the data based on the LIFO last in, first out concept.

How to access the top element in the stack?

We can access the top element in a stack with the top() method. We need to access the top element of the stack.top().

What is the subsequence of a string?

A string ‘string2’ can be called a subsequence of another string ‘string1’ if ‘string2’ can be obtained after deleting zero, one, or more characters from ‘string1’ without disturbing the relative order of the remaining characters.

Can we use the stack in python?

We cannot directly use the stack in python. To apply stack, we have the list data structure in python.

How to remove the top element from the stack?

We have to use the stack.pop() method to remove the top element from the stack.

Conclusion

In this blog, we have discussed how to check if a string is a subsequence of another string with the help of a stack. We have implemented the problem in different programming languages.

To learn more about stack problems, check out the following articles.

• Reverse A String In C
• Reverse a String using Stack
• How To Sort A Stack Using Recursion?
• Difference between Array, Queue & Stack
• Expression Evaluation Using Stack

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String
• Longest common subsequence

You can also consider our Mern Stack Course to give your career an edge over others.

Happy Coding!