# How To Check if One String is a Subsequence of Another?

## Problem Formulation

Description

Given two strings `str1` and `str2`, check if `str1` is a subsequence of `str2`.

subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., `"ace"` is a subsequence of `"abcde"` while `"aec"` is not).

constraints:

• `0 <= str1.length <= 100`
• `0 <= str2.length <= 104`
• `str1` and `str2` consist only of lowercase English letters.

## Example

```Input: str1 = "abc", str2 = "ahbgdc"
Output: True

Input: str1 = "axc", str2 = "ahbgdc"
Output: False```

Border Cases

• If `str1` and `str2` are both empty, then Output → `TRUE`, as empty string a subsequence of another empty string.
• If `str1` → empty and `str2` → not empty, then Output → `TRUE`, as empty string is also a subsequence of any given string.
• If `str1` → not empty and `str2` → empty, then Output → `FALSE`, as non-empty string cannot be subsequence of empty string.
```Input: str1 = "", str2 = ""
Output: True

Input: str1 = "", str2 = "ahbgdc"
Output: True

Input: str1 = "abc", str2 = ""
Output: False```

## Proposed Solution Overview

Traverse through each character in the given strings. There are two cases when you do so:

1. The current characters of both strings are equal. So, move on to the next next index/character of `str1` and `str2`.
2. Current characters of both strings are not equal. So, move on to the next index/character of `str2`. However the index of `str1` remains fixed in this case since the matching character was not found.

The above process is repeated until on of the following criteria’s are satisfied:

1. All characters of `str1` are found to be present in `str2`. The length of `str1` and the current value of `index_str1` will be equal in this case. This denotes that we successfully found the subsequence within the given string. In other words, `str1` is a subsequence of `str2`.
2. All characters of `str2` have been traversed. This means that either the last character of `str1` and `str2` are equal or `str2` is not a subsequence of `str1`.

Diagrammatic representation:

### Solution

```def isSubSequence(str1, str2):
len_str1 = len(str1)
len_str2 = len(str2)
index_str1 = 0
index_str2 = 0
# Traverse both str1 and str2
while index_str1 < len_str1 and index_str2 < len_str2:
# Compare current character of str2 with str1
if str1[index_str1] == str2[index_str2]:
# If matched, then move to next character in str1
index_str1 = index_str1 + 1
index_str2 = index_str2 + 1
return index_str1 == len_str1

val_1 = 'abc'
val_2 = 'ahbgdc'
print(isSubSequence(val_1, val_2))
```

Output:

`True`

Code Explanation:

• `len_str1` and `len_str2` store the length of `str1` and `str2` respectively.
• `index_str1` and `index_str2` are used to store the indices of each character of `str1` and `str2` respectively.
• The `while` loop is used to traverse through the strings until a match is found or all the indices of str2 have been traversed in case of no match.
• The `if statement` compares the current character of `str1` and `str2`.
• In case a match is found, the index of the next character in `str1` is taken into account.
• The value of `index_str1` is incremented at every iteration to traverse through all the letters available in `str1` until the subsequence is found.
• Finally, if the subsequence was found the value stored by `index_str1` will be equal to the length of `str1`.

Dry Run:

The following table illustrates the operation at each iteration within the while loop until the match is found.

### 📹 Video Solution 