Is SubSequence

Easy

0/40

Average time to solve is 10m

Contributed by

28 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
AE
BADE
AB
AC

Sample Output 1:

True
False

Explanation of sample input 1:

Test Case 1:

String ‘STR1’ is ‘AE’ and ‘STR2’ is ‘BADE’. All possible subsequences of ‘BADE’ are-

‘B’, ‘A’, ‘D’, ‘E’, ‘BA’, ‘BD’, ‘BE’, ‘AD’, ‘AE’, ‘DE’, ‘BAD’, ‘BAE’, ‘BDE’, ‘ADE’, ‘BADE’.
Hence ‘AE’ one of the subsequences of ‘BADE’


Test case 2:

String  ‘STR1’ is ‘AB’ and ‘STR2’ is ‘AC’.
There is no way to get string ‘AB’ from string ‘AC’ as character ‘B’ doesn’t exist in string ‘AC’.

Sample Input 2:

2
CB
BCDE
ABC
AHBDGC

Sample Output 2:

False
True

Console