New update is available. Click here to update.

Is SubSequence

Posted: 18 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You have been given two strings ‘STR1’ and ‘STR2’.

Your task is to find if ‘STR1’ is a subsequence of ‘STR2’.

A subsequence of a string is a new string that can be derived from the original string by deleting some characters (can be none) without changing the relative ordering of other characters.

Example:
‘ACE’ is a subsequence of ‘ABCDE’ because ‘ACE’ can be formed by deleting ‘B’ and ‘D’ without changing the relative order of characters. ‘ADB’ is not a subsequence of ‘ABCDE’ because we can get ‘ABD’ from ‘ABCDE’ but not ‘ADB’ and in ‘ADB’ relative order of ‘B’ and ‘D’ are different from original strings.
Note:
1.Strings ‘STR1’ and ‘STR2’ consists only of English uppercases.

2.Length of string ‘STR2’ will always be greater than or equal to the length of string ‘STR1’.

Example:

For example, the given ‘STR1’ is ‘BAE’ and ‘STR2’ is ‘ABADE’. 
String ‘STR1’ is a subsequence of string ‘STR2’ because ‘BAE’ can be formed by deleting ‘A’ and ‘D’ from ‘ABADE’ and the relative ordering of the characters of the string ‘ABADE’ persists.

subsequence

Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains the string ‘STR1’ on a separate line denoting the subsequence that we need to find in 'STR2' and 'N' is the length of 'STR1'.

The second line of each test case contains the string ‘STR2’ on a separate line denoting the string in which we need to find the subsequence and 'M' is the length of 'STR2'.
Output Format
For each test case, print a string ‘True’ if ‘STR1’ is a subsequence of ‘STR2’ otherwise print ‘False’.
Note:
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 50
1 <= N, M <= 10^4

Where N and M denote the lengths of STR1 and STR2respectively. 

Time limit: 1 second