Problem Statement: Let there are two strings S1 and S2. If the S1 is a subsequence of S2 return true otherwise return false.
String S1 is said to be a subsequence of string S2 if S1 is can be obtained from the S2 by deleting some of the characters from S2 without disturbing the relative positions of the remaining characters in S2.
Examples:
Example 1: Input: S1= “tuf”, S2 =”takeuforward” Output: true Explanation: string S1 can be obtained from the S2 by deleting characters a,k,e,o,r,w,a,r,d. Here the relative ordering of characters of S1 is maintained in S2 . ‘t’ appears before ‘u’ and ‘u’ appears before ‘f’. Example 2: Input: S1 = “cdx”,S2 = “coding” Output: false Explanation:‘x’ is not present in S2, So in any way we cannot get S1 by deleting some characters in S2. Example 3: Input: S1 = “fgn” , S2= “faang” Output: false Explanation: All the characters in S1 are in S2 but the relative ordering of characters is S1 is different from S2. In S1 g appears before n, whereas in S2 g appears after n. As relative ordering is different, S1 is not the subsequence of S2.
Solution:
Disclaimer: Don’t Jump Directly to the solution, try it out yourself first.
Solution 1:
Approach: Two pointers
- Take two pointers let’s say i,j pointing to the 0th index of S1 and S2.
- Traverse the two strings until we reach the end of any string.
- In the iteration compare the S1[ i ] and S2[ j ], if S1[ i ] == S2[ j ] that mean we found the character corresponding to S1[ i ] in S2 ,So then increment both i and j.
- If S1[ i ] != S2[ j ] that mean we not found the character corresponding to S1 [ i ] in S2.
- So increment only j.
- After the traversing check whether the ( i == S1.length) if i is equal to S1’s length, It means, we found every character of S1 in S2 without distributing the relative order of S2. Hence return true.
- If (i != S1.length) there are still characters left in S1 and S2 if finished, So S1 cannot be the Subsequence of S2.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
bool isSubsequence(string & S1, string & S2) {
int i = 0, j = 0; // pointers for string S1 and S2
// iterating until reaching end of any one string.
for (; i < S1.length() && j < S2.length(); j++)
if (S1[i] == S2[j])
i++; // incrementing i
return (i == S1.length()); // checking conditon
}
int main()
{
string S1 = "tuf", S2 = "takeuforward";
if (isSubsequence(S1, S2))
cout << S1 << " is subsequence of " << S2 << endl;
else
cout << S1 << " is not subsequence of " << S2 << endl;
return 0;
}
Output:
tuf is subsequence of takeuforward
Time Complexity : O( min( |S1| , |S2| ) ) Because the for loop runs until the end of any string is reached. The end of the string with minimum length is reached first. So Time complexity is the minimum length of S1 and S2.
Space Complexity: O(1) We are not using any extra space.
Java Code
import java.util.*;
class TUF{
static boolean isSubsequence(String S1, String S2) {
int i = 0, j = 0; // pointers for string S1 and S2
// iterating until reaching end of any one string.
for (; i < S1.length() && j < S2.length(); j++)
if (S1.charAt(i) == S2.charAt(j))
i++; // incrementing i
return (i == S1.length()); // checking conditon
}
public static void main(String args[])
{
String S1 = "tuf", S2 = "takeuforward";
if (isSubsequence(S1, S2))
System.out.println(S1+" is subsequence of "+S2);
else
System.out.println(S1+" is not subsequence of "+S2);
}
}
Output:
tuf is subsequence of takeuforward
Time Complexity : O( min( |S1| , |S2| ) ) Because the for loop runs until the end of any string is reached. The end of the string with minimum length is reached first. So Time complexity is the minimum length of S1 and S2.
Space Complexity: O(1) We are not using any extra space.
Solution 2:
Approach: Recursion
Intuition is the same as discussed in Two pointers. But instead of the loop, we use recursion to do the work. Any loop can be converted into tail recursion and vice versa. Traverse through both strings from one end to another, say from rightmost to leftmost {we can also travel from leftmost to rightmost but the parameters required will be more}.
If we found a matching character we move ahead in both strings, otherwise we move ahead only in S2.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
bool isSubsequence(string & s1, string & s2,int n,int m) {
if (n == 0)
return true; // we reach the end of the s1,so return true;
if (m == 0)
return false;
// we reached end of S2,with characters
// remaining in s1,so return false
if (s1[n - 1] == s2[m - 1])
// moving ahead in both strings
return isSubsequence(s1, s2, n - 1, m - 1);
else
// moving ahead in only S2
return isSubsequence(s1, s2, n, m - 1);
}
int main()
{
string S1 = "tuf", S2 = "takeuforward";
if (isSubsequence(S1, S2,S1.length(),S2.length()))
cout << S1 << " is subsequence of " << S2 << endl;
else
cout << S1 << " is not subsequence of " << S2 << endl;
return 0;
}
Output:
tuf is subsequence of takeuforward.
Time Complexity: O( min( |S1|, |S2| ) ) Because the recursion calls are made until the end of any string is reached. The end of the string with minimum length is reached first. So Time complexity is the minimum length of S1 and S2.
Space Complexity : O( min( |S1| , |S2| ) ) Auxiliary stack space.
Java Code
import java.util.*;
class TUF{
static boolean isSubsequence(String s1, String s2,int n,int m) {
if (n == 0)
return true; // we reach the end of the s1, so return true;
if (m == 0)
// we reached end of S2, with characters
// remaining in s1, so return false
return false;
if (s1.charAt(n - 1) == s2.charAt(m - 1))
// moving ahead in both strings
return isSubsequence(s1, s2, n - 1, m - 1);
else
// moving ahead in only S2
return isSubsequence(s1, s2, n, m - 1);
}
public static void main(String args[])
{
String S1 = "tuf", S2 = "takeuforward";
if (isSubsequence(S1, S2,S1.length(),S2.length()))
System.out.println(S1+" is subsequence of "+S2);
else
System.out.println(S1+" is not subsequence of "+S2);
}
}
Output:
tuf is subsequence of takeuforward.
Time Complexity: O( min( |S1|, |S2| ) ) Because the recursion calls are made until the end of any string is reached. The end of the string with minimum length is reached first. So Time complexity is the minimum length of S1 and S2.
Space Complexity : O( min( |S1| , |S2| ) ) Auxiliary stack space.
Solution 3 : Dynammic Programming
Prerequisite: Longest Common subsequence in two strings.
Approach: Find the longest common subsequence in S1 and S2 if the length of the longest common subsequence is equal to the length of S1, then S1 is the subsequence of S2.
Code:
C++Code
// function to return the length of the longest
// common subsequence in strings S1 and S2
#include<bits/stdc++.h>
using namespace std;
int isSubsequence(string & s1, string & s2, int i, int j,
vector < vector < int >> & dp) {
if (i < 0 || j < 0)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (s1[i] == s2[j])
return dp[i][j] = 1 + isSubsequence(s1, s2, i - 1, j - 1, dp);
return dp[i][j] = max(isSubsequence(s1, s2, i - 1, j, dp),
isSubsequence(s1, s2, i, j - 1, dp));
}
int main()
{
string S1 = "tuf", S2 = "takeuforward";
int n = S1.length(), m = S2.length();
vector < vector < int >> dp(n, vector < int > (m, -1));
// if length of longest common subsequence is equal
// to S1's length then S1 is subsequence of S2,else not.
if (isSubsequence(S1, S2, n - 1, m - 1, dp) == n)
cout << S1 << " is subsequence of " << S2 << endl;
else
cout << S1 << " is not subsequence of " << S2 << endl;
return 0;
}
Output:
tuf is subsequence of takeuforward.
Time Complexity : O( |S1| * |S2| )
Space Complexity : O( |S1| * |S2| ) {2D vector space} + O( |S1| + |S2| ) {stack space}
Java Code
// function to return the length of the
// longest common subsequence in strings S1 and S2
import java.util.*;
class TUF{
static int isSubsequence(String s1, String s2, int i,
int j, int[][] dp) {
if (i < 0 || j < 0)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (s1.charAt(i) == s2.charAt(j))
return dp[i][j] = 1 + isSubsequence(s1, s2, i - 1, j - 1, dp);
return dp[i][j] = Math.max(isSubsequence(s1, s2, i - 1, j, dp),
isSubsequence(s1, s2, i, j - 1, dp));
}
public static void main(String args[])
{
String S1 = "tuf", S2 = "takeuforward";
int n = S1.length(), m = S2.length();
int dp[][]=new int[n][m];
for(int row[]:dp)
Arrays.fill(row,-1);
if (isSubsequence(S1, S2, n - 1, m - 1, dp) == n)
// if length of longest common subsequence is
// equal to S1's length then S1 is subsequence of S2,
// else not.
System.out.println(S1+" is subsequence of "+S2);
else
System.out.println(S1+" is not subsequence of "+S2);
}
}
Output:
tuf is subsequence of takeuforward.
Time Complexity : O( |S1| * |S2| )
Space Complexity : O( |S1| * |S2| ) {2D Array} + O( |S1| + |S2| ) {stack space}
Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article