Given two strings str1 and str2, find if the first string is a Subsequence of the second string, i.e. if str1 is a subsequence of str2.
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: str1 = “AXY”, str2 = “ADXCPY”
Output: True (str1 is a subsequence of str2)Input: str1 = “AXY”, str2 = “YADXCP”
Output: False (str1 is not a subsequence of str2)Input: str1 = “gksrek”, str2 = “neveropen”
Output: True (str1 is a subsequence of str2)
First String is a Subsequence of second by Recursion:
The idea is simple, traverse both strings from one side to another side (say from rightmost character to leftmost). If we find a matching character, move ahead in both strings. Otherwise, move ahead only in str2.
Below is the Implementation of the above idea:
C++
// Recursive C++ program to check// if a string is subsequence// of another string#include <cstring>#include <iostream>using namespace std;// Returns true if str1[] is a// subsequence of str2[]. m is// length of str1 and n is length of str2bool isSubSequence(char str1[], char str2[], int m, int n){ // Base Cases if (m == 0) return true; if (n == 0) return false; // If last characters of two // strings are matching if (str1[m - 1] == str2[n - 1]) return isSubSequence(str1, str2, m - 1, n - 1); // If last characters are // not matching return isSubSequence(str1, str2, m, n - 1);}// Driver program to check whether str1 is subsequence of// str2 or not.int main(){ char str1[] = "gksrek"; char str2[] = "neveropen"; int m = strlen(str1); int n = strlen(str2); isSubSequence(str1, str2, m, n) ? cout << "Yes " : cout << "No"; return 0;} |
Java
// Recursive Java program to check if a string// is subsequence of another stringimport java.io.*;class SubSequence { // Returns true if str1[] is a subsequence of str2[] // m is length of str1 and n is length of str2 static boolean isSubSequence(String str1, String str2, int m, int n) { // Base Cases if (m == 0) return true; if (n == 0) return false; // If last characters of two strings are matching if (str1.charAt(m - 1) == str2.charAt(n - 1)) return isSubSequence(str1, str2, m - 1, n - 1); // If last characters are not matching return isSubSequence(str1, str2, m, n - 1); } // Driver program public static void main(String[] args) { String str1 = "gksrek"; String str2 = "neveropen"; int m = str1.length(); int n = str2.length(); boolean res = isSubSequence(str1, str2, m, n); if (res) System.out.println("Yes"); else System.out.println("No"); }}// Contributed by Pramod Kumar |
Python3
# Recursive Python program to check# if a string is subsequence# of another string# Returns true if str1[] is a# subsequence of str2[].def isSubSequence(string1, string2, m, n): # Base Cases if m == 0: return True if n == 0: return False # If last characters of two # strings are matching if string1[m-1] == string2[n-1]: return isSubSequence(string1, string2, m-1, n-1) # If last characters are not matching return isSubSequence(string1, string2, m, n-1)# Driver program to test the above functionstring1 = "gksrek"string2 = "neveropen"if isSubSequence(string1, string2, len(string1), len(string2)): print("Yes")else: print("No")# This code is contributed by BHAVYA JAIN |
C#
// Recursive C# program to check if a string// is subsequence of another stringusing System;class GFG { // Returns true if str1[] is a // subsequence of str2[] m is // length of str1 and n is length // of str2 static bool isSubSequence(string str1, string str2, int m, int n) { // Base Cases if (m == 0) return true; if (n == 0) return false; // If last characters of two strings // are matching if (str1[m - 1] == str2[n - 1]) return isSubSequence(str1, str2, m - 1, n - 1); // If last characters are not matching return isSubSequence(str1, str2, m, n - 1); } // Driver program public static void Main() { string str1 = "gksrek"; string str2 = "neveropen"; int m = str1.Length; int n = str2.Length; bool res = isSubSequence(str1, str2, m, n); if (res) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed by nitin mittal. |
Javascript
<script>// Recursive Javascript program to check if // a string is subsequence of another string// Returns true if str1[] is a// subsequence of str2[] m is// length of str1 and n is length// of str2function isSubSequence(str1, str2, m, n){ // Base Cases if (m == 0) return true; if (n == 0) return false; // If last characters of two strings // are matching if (str1[m - 1] == str2[n - 1]) return isSubSequence(str1, str2, m - 1, n - 1); // If last characters are not matching return isSubSequence(str1, str2, m, n - 1);}// Driver codelet str1 = "gksrek";let str2 = "neveropen";let m = str1.length;let n = str2.length;let res = isSubSequence(str1, str2, m, n);if (res) document.write("Yes");else document.write("No"); // This code is contributed by divyesh072019</script> |
PHP
<?php// Recursive PHP program to check// if a string is subsequence of // another string// Returns true if str1[] is a // subsequence of str2[]. m is// length of str1 and n is // length of str2function isSubSequence($str1, $str2, $m, $n){ // Base Cases if ($m == 0) return true; if ($n == 0) return false; // If last characters of two // strings are matching if ($str1[$m - 1] == $str2[$n - 1]) return isSubSequence($str1, $str2, $m - 1, $n - 1); // If last characters // are not matching return isSubSequence($str1, $str2, $m, $n - 1);}// Driver Code$str1= "gksrek";$str2 = "neveropen";$m = strlen($str1);$n = strlen($str2);$t = isSubSequence($str1, $str2, $m, $n) ? "Yes ": "No";if($t = true) echo "Yes";else echo "No";// This code is contributed by ajit?> |
Output
Yes
Time Complexity: O(N), The recursion will call at most N times.
Auxiliary Space: O(1), Function call stack space, because it is a tail recursion.
First String is a Subsequence of second using Two Pointers (Iterative):
The idea is to use two pointers, one pointer will start from start of str1 and another will start from start of str2. If current character on both the indexes are same then increment both pointers otherwise increment the pointer which is pointing str2.
Follow the steps below to solve the problem:
- Initialize the pointers i and j with zero, where i is the pointer to str1 and j is the pointer to str2.
- If str1[i] = str2[j] then increment both i and j by 1.
- Otherwise, increment only j by 1.
- If i reaches the end of str1 then return TRUE else return FALSE.
Below is the implementation of the above approach
C++
/*Iterative C++ program to checkIf a string is subsequence of another string*/#include <bits/stdc++.h>using namespace std;/*Returns true if s1 is subsequence of s2*/bool issubsequence(string& s1, string& s2){ int n = s1.length(), m = s2.length(); int i = 0, j = 0; while (i < n && j < m) { if (s1[i] == s2[j]) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n;}int main(){ string s1 = "gksrek"; string s2 = "neveropen"; if (issubsequence(s1, s2)) cout << "gksrek is subsequence of neveropen" << endl; else cout << "gksrek is not a subsequence of " "neveropen" << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { /*Iterative Java program to checkIf a String is subsequence of another String*/ /*Returns true if s1 is subsequence of s2*/ static boolean issubsequence(String s1, String s2) { int n = s1.length(), m = s2.length(); int i = 0, j = 0; while (i < n && j < m) { if (s1.charAt(i) == s2.charAt(j)) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n; } public static void main(String args[]) { String s1 = "gksrek"; String s2 = "neveropen"; if (issubsequence(s1, s2)) System.out.println( "gksrek is subsequence of geekforneveropen"); else System.out.println( "gksrek is not a subsequence of geekforneveropen"); }}// This code is contributed by shinjanpatra. |
Python3
# Iterative JavaScript program to check# If a string is subsequence of another string# Returns true if s1 is subsequence of s2def issubsequence(s1, s2): n, m = len(s1), len(s2) i, j = 0, 0 while (i < n and j < m): if (s1[i] == s2[j]): i += 1 j += 1 # If i reaches end of s1,that mean we found all # characters of s1 in s2, # so s1 is subsequence of s2, else not return i == n# driver codes1 = "gksrek"s2 = "neveropen"if (issubsequence(s1, s2)): print("gksrek is subsequence of geekforneveropen")else: print("gksrek is not a subsequence of geekforneveropen")# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;class GFG { /*Returns true if s1 is subsequence of s2*/ static bool issubsequence(string s1, string s2) { int n = s1.Length, m = s2.Length; int i = 0, j = 0; while (i < n && j < m) { if (s1[i] == s2[j]) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n; } public static void Main(string[] args) { string s1 = "gksrek"; string s2 = "neveropen"; if (issubsequence(s1, s2)) Console.WriteLine(s1 + " is subsequence of " + s2); else Console.WriteLine( s1 + " is not a subsequence of " + s2); }}// This code is contributed by phasing17. |
Javascript
<script>/*Iterative JavaScript program to checkIf a string is subsequence of another string*//*Returns true if s1 is subsequence of s2*/function issubsequence(s1, s2){ let n = s1.length, m = s2.length; let i = 0, j = 0; while (i < n && j < m) { if (s1[i] == s2[j]) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n;}// driver codelet s1 = "gksrek";let s2 = "neveropen";if (issubsequence(s1, s2)) document.write("gksrek is subsequence of geekforneveropen","</br>");else document.write("gksrek is not a subsequence of geekforneveropen","</br>");// This code is contributed by shinjanpatra</script> |
Output
gksrek is subsequence of neveropen
Time Complexity: O(max(n,m)), where n,m is the length of given string s1 and s2 respectively.
Auxiliary Space: O(1)
Another Approach for First String is a Subsequence of second using Queue:
Strategy: Use Queue to store the shorter string, pop one element at a time from queue and check if there’s a match in the longer string
proceed with poping elements only if theres a match, if Queue is empty at the end, we have a match.
C++
/*Iterative C++ program to checkIf a string is subsequence of another string*/#include <bits/stdc++.h>using namespace std;/*Returns true if t is subsequence of s*/bool issubsequence(string& s, string& t){ queue<char> q; int cnt = 0; // push the string t in queue; for (int i = 0; i < t.size(); i++) { q.push(t[i]); } int i = 0; // traverse throgh the entire queue while (!q.empty()) { // check if the ith element in s is equal to front // element if (s[i] == q.front()) { cnt++; i++; } // pop element of queue after each iteration q.pop(); } // check for the cnt length if (cnt == s.size()) return true; else return false;}int main(){ string s1 = "gksrek"; string s2 = "neveropen"; if (issubsequence(s1, s2)) cout << "gksrek is subsequence of neveropen" << endl; else cout << "gksrek is not a subsequence of " "neveropen" << endl; return 0;} |
Java
/*Iterative Java program to checkIf a string is subsequence of another string*/import java.util.LinkedList;import java.util.Queue;public class Main { /*Returns true if t is subsequence of s*/ public static boolean isSubsequence(String s, String t) { Queue<Character> q = new LinkedList<>(); int cnt = 0; // push the string t into the queue for (int i = 0; i < t.length(); i++) { q.add(t.charAt(i)); } int i = 0; // traverse through the entire queue while (!q.isEmpty() && i < s.length()) { // check if the ith element in s is equal // to the front element if (s.charAt(i) == q.peek()) { cnt++; i++; } // remove element from the queue after each iteration q.poll(); } // check if all characters in s were found return cnt == s.length(); } public static void main(String[] args) { String s1 = "gksrek"; String s2 = "neveropen"; if (isSubsequence(s1, s2)) System.out.println("gksrek is a subsequence of neveropen"); else System.out.println("gksrek is not a subsequence of neveropen"); }} |
Python
# Iterative Python program to check# if a string is subsequence of another stringfrom queue import Queue# Returns true if t is subsequence of sdef IsSubsequence(s, t): q = Queue() cnt = 0 # push the string t into the queue for x in t: q.put(x) i = 0 # traverse through the entire queue while not q.empty() and i < len(s): # check if the ith element in s is equal to the front element if s[i] == q.queue[0]: cnt += 1 i += 1 # remove element from the queue after each iteration q.get() # check if all characters in s were found return cnt == len(s)s1 = "gksrek"s2 = "neveropen"if IsSubsequence(s1, s2): print("gksrek is a subsequence of neveropen")else: print("gksrek is not a subsequence of neveropen") |
C#
/*Iterative C# program to checkIf a string is subsequence of another string*/using System;using System.Collections.Generic;class GFG{ /* Returns true if t is subsequence of s */ public static bool IsSubsequence(string s, string t) { Queue<char> q = new Queue<char>(); int cnt = 0; // push the string t into the queue for (int x = 0; x < t.Length; x++) { q.Enqueue(t[x]); } int i = 0; // traverse through the entire queue while (q.Count > 0 && i < s.Length) { // check if the ith element in s is equal to the front element if (s[i] == q.Peek()) { cnt++; i++; } // remove element from the queue after each iteration q.Dequeue(); } // check if all characters in s were found return cnt == s.Length; } public static void Main(string[] args) { string s1 = "gksrek"; string s2 = "neveropen"; if (IsSubsequence(s1, s2)) Console.WriteLine("gksrek is a subsequence of neveropen"); else Console.WriteLine("gksrek is not a subsequence of neveropen"); }} |
Javascript
// Returns true if t is subsequence of sfunction isSubsequence(s, t) { let q = []; let cnt = 0; // push the string t into the queue for (let x = 0; x < t.length; x++) { q.push(t[x]); } let i = 0; // traverse through the entire queue while (q.length > 0 && i < s.length) { // check if the ith element in s is equal to the front element if (s[i] === q[0]) { cnt++; i++; } // remove element from the queue after each iteration q.shift(); } // check if all characters in s were found return cnt === s.length;}const s1 = "gksrek";const s2 = "neveropen";if (isSubsequence(s1, s2)) console.log("gksrek is a subsequence of neveropen");else console.log("gksrek is not a subsequence of neveropen"); |
Output
gksrek is subsequence of neveropen
Time Complexity: O(n), as we are linearly traversing both the strings entirely.
Auxiliary Space: O(n),for extra space occupied by queue.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
