Check if a string is a subsequence of another string ( using Stacks )
Last Updated :
07 Nov, 2023
Given a string S, the task is to check if the string target is a subsequence of string S or not, using a Stack.
Examples:
Input: S = ”KOTTAYAM”, target = ”KOTA”
Output: Yes
Explanation: “KOTA” is a subsequence of “KOTTAYAM”.
Input: S = ”GEEKSFORGEEKS”, target =”FORFOR”
Output: No
Approach: Follow the steps to solve the problem:
target pushed into the stack
Traversing in S
Traversing in S
Popping from stack
Traversing in S
Popping from stack
Traversing in st
Popping from stack
Traversing in S
Stack becomes emptyBelow is the implementation of the above approach:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if target
// is a subsequence of string S
void checkforSubsequence(string S,
string target)
{
// Declare a stack
stack<char> s;
// Push the characters of
// target into the stack
for (int i = 0; i < target.size(); i++) {
s.push(target[i]);
}
// Traverse the string S in reverse
for (int i = (int)S.size() - 1; i >= 0; i--) {
// If the stack is empty
if (s.empty()) {
cout << "Yes" << endl;
return;
}
// if S[i] is same as the
// top of the stack
if (S[i] == s.top()) {
// Pop the top of stack
s.pop();
}
}
// Stack s is empty
if (s.empty())
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// Driver Code
int main()
{
string S = "KOTTAYAM";
string target = "KOTA";
checkforSubsequence(S, target);
return 0;
}
// Java approach for the above approach
import java.util.Stack;
public class GFG {
// Function to check if target
// is a subsequence of string S
static void checkforSubsequence(String S, String target)
{
// Declare a stack
Stack<Character> s = new Stack<>();
// Push the characters of
// target into the stack
for (int i = 0; i < target.length(); i++) {
s.push(target.charAt(i));
}
// Traverse the string S in reverse
for (int i = (int)S.length() - 1; i >= 0; i--) {
// If the stack is empty
if (s.empty()) {
System.out.println("Yes");
return;
}
// if S[i] is same as the
// top of the stack
if (S.charAt(i) == s.peek()) {
// Pop the top of stack
s.pop();
}
}
// Stack s is empty
if (s.empty())
System.out.println("Yes");
else
System.out.println("No");
}
// Driver Code
public static void main(String[] args)
{
String S = "KOTTAYAM";
String target = "KOTA";
checkforSubsequence(S, target);
}
}
// This code is contributed by abhinavjain194
# Python3 program for the above approach
# Function to check if target
# is a subsequence of string S
def checkforSubsequence(S, target):
# Declare a stack
s = []
# Push the characters of
# target into the stack
for i in range(len(target)):
s.append(target[i])
# Traverse the string S in reverse
for i in range(len(S) - 1, -1, -1):
# If the stack is empty
if (len(s) == 0):
print("Yes")
return
# If S[i] is same as the
# top of the stack
if (S[i] == s[-1]):
# Pop the top of stack
s.pop()
# Stack s is empty
if (len(s) == 0):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == "__main__":
S = "KOTTAYAM"
target = "KOTA"
checkforSubsequence(S, target)
# This code is contributed by ukasp
// C# approach for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if target
// is a subsequence of string S
static void checkforSubsequence(String S,
String target)
{
// Declare a stack
Stack<char> s = new Stack<char>();
// Push the characters of
// target into the stack
for(int i = 0; i < target.Length; i++)
{
s.Push(target[i]);
}
// Traverse the string S in reverse
for(int i = (int)S.Length - 1; i >= 0; i--)
{
// If the stack is empty
if (s.Count == 0)
{
Console.WriteLine("Yes");
return;
}
// If S[i] is same as the
// top of the stack
if (S[i] == s.Peek())
{
// Pop the top of stack
s.Pop();
}
}
// Stack s is empty
if (s.Count == 0)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
// Driver Code
public static void Main(String[] args)
{
String S = "KOTTAYAM";
String target = "KOTA";
checkforSubsequence(S, target);
}
}
// This code is contributed by shikhasingrajput
<script>
// JavaScript Program for the above approach
// Function to check if target
// is a subsequence of string S
function checkforSubsequence(S, target)
{
// Declare a stack
var s = [];
// Push the characters of
// target into the stack
for (var i = 0; i < target.length; i++) {
s.push(target[i]);
}
// Traverse the string S in reverse
for (var i = S.length - 1; i >= 0; i--) {
// If the stack is empty
if (s.length==0) {
document.write( "Yes");
return;
}
// if S[i] is same as the
// top of the stack
if (S[i] == s[s.length-1]) {
// Pop the top of stack
s.pop();
}
}
// Stack s is empty
if (s.length==0)
document.write( "Yes" );
else
document.write( "No" );
}
// Driver Code
var S = "KOTTAYAM";
var target = "KOTA";
checkforSubsequence(S, target);
</script>
Time Complexity : O(N)
Auxiliary Space : O(N)
Approach 2: Using the find() function
Another approach to check if a string is a subsequence of another string is to use the find() function. We can call find() on the second string to find the index of the first occurrence of the first character of the first string. Then, we can iterate over the first string and call find() on the second string with the starting index set to the index of the previous character plus one. If find() returns string::npos, it means that the current character in the first string is not present in the second string and hence the first string is not a subsequence of the second string.
Define a function that takes two string arguments s1 and s2.
Initialize an integer variable index to -1. This will be used to keep track of the starting index for each find() call.
Iterate over each character c in s1 using a range-based for loop.
Call the find() function on s2 with the arguments c and index + 1. The second argument specifies the starting index for the search, which is the index of the previous character plus one.
If find() returns string::npos, which indicates that the character was not found in s2, return false immediately, as s1 is not a subsequence of s2.
If find() returns a valid index, update index to the returned value.
After iterating over all the characters in s1, return true, as s1 is a subsequence of s2.
C++
#include <iostream>
#include <string>
using namespace std;
bool isSubsequence(string s1, string s2) {
int index = -1;
for (char c : s1) {
index = s2.find(c, index + 1);
if (index == string::npos) {
return false;
}
}
return true;
}
int main() {
string s1 = "KOTA";
string s2 = "KOTTAYAM";
bool check = isSubsequence(s1, s2) ;
if(check){
cout<<" yes";
}
else{
cout<<"no";
}
return 0;
}
import java.util.*;
public class GFG {
public static boolean isSubsequence(String s1, String s2) {
// Initialize index to -1
int index = -1;
// Loop through each character in s1
for (char c : s1.toCharArray()) {
// Find the index of the current character in s2
index = s2.indexOf(c, index + 1);
// If the character is not found, return false
if (index == -1) {
return false;
}
}
return true; // All characters are found, return true
}
// Driver Code
public static void main(String[] args) {
// input taken
String s1 = "KOTA";
String s2 = "KOTTAYAM";
boolean check = isSubsequence(s1, s2);
// Print "yes" if s1 is a subsequence of s2
if (check) {
System.out.println("yes");
}
// Print "no" if s1 is not a subsequence of s2
else {
System.out.println("no");
}
}
}
def isSubsequence(s1, s2):
index = -1
for c in s1:
index = s2.find(c, index + 1)
if index == -1:
return False
return True
s1 = "KOTA"
s2 = "KOTTAYAM"
check = isSubsequence(s1, s2)
if check:
print("yes")
else:
print("no")
using System;
public class Program
{
// Function to check if s1 is a subsequence of s2
static bool IsSubsequence(string s1, string s2)
{
int index = -1;
foreach (char c in s1)
{
// Search for the character 'c' in s2, starting from index + 1
index = s2.IndexOf(c, index + 1);
// If 'c' is not found in s2, return false
if (index == -1)
{
return false;
}
}
return true;
}
public static void Main()
{
string s1 = "KOTA";
string s2 = "KOTTAYAM";
// Check if s1 is a subsequence of s2
bool check = IsSubsequence(s1, s2);
// Print the result
if (check)
{
Console.WriteLine("Yes, s1 is a subsequence of s2");
}
else
{
Console.WriteLine("No, s1 is not a subsequence of s2");
}
}
}
function isSubsequence(s1, s2) {
// Initialize index to -1
let index = -1;
// Loop through each character in s1
for (const c of s1) {
// Find the index of the current character in s2
index = s2.indexOf(c, index + 1);
// If the character is not found, return false
if (index === -1) {
return false;
}
}
return true; // All characters are found, return true
}
// Driver Code
const s1 = "KOTA";
const s2 = "KOTTAYAM";
const check = isSubsequence(s1, s2);
// Print "yes" if s1 is a subsequence of s2
if (check) {
console.log("yes");
}
// Print "no" if s1 is not a subsequence of s2
else {
console.log("no");
}
// This code is contributed by shivamgupta310570
Time Complexity : O(M*N)
Auxiliary Space : O(1)
Similar Reads
Check if a string is substring of another
Given two strings txt and pat, the task is to find if pat is a substring of txt. If yes, return the index of the first occurrence, else return -1. Examples : Input: txt = "geeksforgeeks", pat = "eks"Output: 2Explanation: String "eks" is present at index 2 and 9, so 2 is the smallest index. Input: tx
8 min read
Check if the given string is shuffled substring of another string
Given strings str1 and str2. The task is to find if str1 is a substring in the shuffled form of str2 or not. Print "YES" if str1 is a substring in shuffled form of str2 else print "NO". Example Input: str1 = "onetwofour", str2 = "hellofourtwooneworld" Output: YES Explanation: str1 is substring in sh
15 min read
Check if a string can be obtained by appending subsequences of another string
Given two strings str1 and str2 of lengths N and M respectively, the task is to check if str2 can be formed by appending subsequences of str1 multiple times. If possible, print the minimum number of append operations required. Otherwise, print -1. Examples: Input: str1 = "abb", str2 = "ababbbbb"Outp
8 min read
Print all subsequences of a string using ArrayList
Given a string str, the task is to print all the sub-sequences of str. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.Examples: Input: str = "abc" Output: a b ab c ac bc abcInput: str = "geek"
8 min read
Check if one string is subsequence of other
Given two strings s1 and s2, find if the first string is a Subsequence of the second string, i.e. if s1 is a subsequence of s2. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Examples : Input: s1 =
10 min read
Javascript Program To Check If A String Is Substring Of Another
Given two strings s1 and s2, find if s1 is a substring of s2. If yes, return the index of the first occurrence, else return -1. Examples :Â Input: s1 = "for", s2 = "geeksforgeeks" Output: 5 Explanation: String "for" is present as a substring of s2. Input: s1 = "practice", s2 = "geeksforgeeks" Output
2 min read
Count of substrings of a string containing another given string as a substring | Set 2
Given two strings S and T of length N and M respectively, the task is to count the number of substrings of S that contains the string T in it as a substring. Examples: Input: S = “dabcâ€, T = “abâ€Output: 4Explanation:Substrings of S containing T as a substring are: S[0, 2] = “dabâ€S[1, 2] = “abâ€S[1, 3
8 min read
Print all occurrences of a string as a substring in another string
Given two strings, str1 and str2, the task is to print the indices(Consider, indices starting from 0) of the occurrence of str2 in str1. If no such index occurs, print "NONE". Examples: Input : GeeksforGeeks GeeksOutput : 0 8Input : GFG gOutput : NONEApproach 1 (Naive Approach): A simple solution is
12 min read
Check if a string is present in the given Linked List as a subsequence
Given a string S of size N and a linked list, the task is to check if the linked list contains a string as a subsequence. Print Yes if it contains the subsequence otherwise print No. Example: Input: S = "bad", Linked List: b -> r -> a -> d -> NULLOutput: Yes Input: S = "bad", Linked List
5 min read
Find length of longest subsequence of one string which is substring of another string
Given two strings X and Y. The task is to find the length of the longest subsequence of string X which is a substring in sequence Y. Examples: Input : X = "ABCD", Y = "BACDBDCD"Output : 3Explanation: "ACD" is longest subsequence of X which is substring of Y. Input : X = "A", Y = "A"Output : 1 Perqui
15+ min read