Given two strings find if the first string is a subsequence of second

Through string subsequence, Suppose two strings str1 and str2, then find 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 (source: wiki). So the time complexity is linear.

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 = "geeksforgeeks"
Output: True (str1 is a subsequence of str2)

The idea is simple, we traverse both the strings from one side to other side means say from rightmost character to leftmost, then if we find the matching characters, we move ahead both the strings. Otherwise we move ahead only in str2.

So the recursive principle of above idea is:

Recursive C++ program to check if a string is a subsequence of another string.

// 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 str2
bool 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 test methods of graph class
int main()
{
	char str1[] = "gksrek";
	char str2[] = "geeksforgeeks";
	int m = strlen(str1);
	int n = strlen(str2);
	isSubSequence(str1, str2, m, n) ? cout << "Yes "
									: cout << "No";
	return 0;
}

Recursive Java program to check if a string is a subsequence of another string.

// Recursive Java program to check if a string
// is subsequence of another string
import 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 = "geeksforgeeks";
		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

Recursive Python program to check if a string is a subsequence of another string.

# 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 function
string1 = "gksrek"
string2 = "geeksforgeeks"

if isSubSequence(string1, string2, 0, 0):
	print "Yes"
else:
	print "No"

# This code is contributed by BHAVYA JAIN

Recursive C#program to check if a string is a subsequence of another string.

// Recursive C# program to check if a string
// is subsequence of another string
using 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 = "geeksforgeeks";
		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.

Recursive PHP program to check if a string is a subsequence of another string.

<?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 str2

function 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 = "geeksforgeeks";
$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

Then now is the Iterative Implementation:

Iterative C++ program to check if a string is a subsequence of another string.

// Iterative 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 str2
bool isSubSequence(char str1[], char str2[], int m, int n)
{
	int j = 0; // For index of str1 (or subsequence

	// Traverse str2 and str1, and
	// compare current character
	// of str2 with first unmatched char
	// of str1, if matched
	// then move ahead in str1
	for (int i = 0; i < n && j < m; i++)
		if (str1[j] == str2[i])
			j++;

	// If all characters of str1 were found in str2
	return (j == m);
}

// Driver program to test methods of graph class
int main()
{
	char str1[] = "gksrek";
	char str2[] = "geeksforgeeks";
	int m = strlen(str1);
	int n = strlen(str2);
	isSubSequence(str1, str2, m, n) ? cout << "Yes "
									: cout << "No";
	return 0;
}

Iterative Java program to check if a string is a subsequence of another string.

// Iterative Java program to check if a string
// is subsequence of another string
import java.io.*;

class GFG {

	// 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)
	{
		int j = 0;

		// Traverse str2 and str1, and compare
		// current character of str2 with first
		// unmatched char of str1, if matched
		// then move ahead in str1
		for (int i = 0; i < n && j < m; i++)
			if (str1.charAt(j) == str2.charAt(i))
				j++;

		// If all characters of str1 were found
		// in str2
		return (j == m);
	}

	// Driver program to test methods of
	// graph class
	public static void main(String[] args)
	{
		String str1 = "gksrek";
		String str2 = "geeksforgeeks";
		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");
	}
}

// This code is contributed by Pramod Kumar

Iterative Python program to check if a string is a subsequence of another string.

# Iterative Python program to check if a
# string is subsequence of another string

# Returns true if str1 is a subsequence of str2

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)

	j = 0 # Index of str1
	i = 0 # Index of str2

	# Traverse both str1 and str2
	# Compare current character of str2 with
	# first unmatched character of str1
	# If matched, then move ahead in str1

	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j+1
		i = i + 1

	# If all characters of str1 matched,
	# then j is equal to m
	return j == m

# Driver Program


str1 = "gksrek"
str2 = "geeksforgeeks"

print "Yes" if isSubSequence(str1, str2) else "No"

# Contributed by Harshit Agrawal

Iterative C# program to check if a string is a subsequence of another string.

// Iterative C# program to check if a string
// is subsequence of another string
using 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)
	{
		int j = 0;
		
		// Traverse str2 and str1, and compare
		// current character of str2 with first
		// unmatched char of str1, if matched
		// then move ahead in str1
		for (int i = 0; i < n && j < m; i++)
			if (str1[j] == str2[i])
				j++;

		// If all characters of str1 were found
		// in str2
		return (j == m);
	}
	
	// Driver program to test methods of
	// graph class
	public static void Main ()
	{
		String str1 = "gksrek";
		String str2 = "geeksforgeeks";
		int m = str1.Length;
		int n = str2.Length;
		bool res = isSubSequence(str1, str2, m, n);
		
		if(res)
			Console.WriteLine("Yes");
		else
			Console.WriteLine("No");
	}
}

// This code is contributed by anuj_67.

Iterative PHP program to check if a string is a subsequence of another string.

<?php
// Iterative 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 str2
function isSubSequence($str1, $str2,
							$m, $n)
{
	// For index of str1
	$j = 0;
	
	// Traverse str2 and str1,
	// and compare current
	// character of str2 with
	// first unmatched char of
	// str1, if matched then
	// move ahead in str1
	for($i = 0; $i < $n and
		$j < $m; $i++)
		if ($str1[$j] == $str2[$i])
			$j++;
	
	// If all characters of
	// str1 were found in str2
	return ($j == $m);
}

	// Driver Code
	$str1 = "gksrek";
	$str2 = "geeksforgeeks";
	$m = strlen($str1);
	$n = strlen($str2);
	
	if(isSubSequence($str1, $str2, $m, $n))
		echo "Yes ";
	else
		echo "No";

// This code is contributed by anuj_67.
?>

Output: