Is Subsequence

LeetCode Problem #392 (Easy)

Problem Statement

Given a string s and a string t, check if s is a subsequence of t.

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

Constraints:

0 <= s.length <= 100

0 <= t.length <= 10^4

Both strings consists only of lowercase characters.

Testcases

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Prerequisite Knowledge

Subsequence

A subsequence is a sequence which can be derived from another sequence using zero or more elements while maintaining the relative order of the elements in the original sequence.

Example

Let us consider the string "coding".

The sequence of elements in this string is as follows:

c o d i n g
1 2 3 4 5 6

The characters in a subsequence of this sequence do not have to be located consecutive to one another, but the relative order of the characters must be maintained.

Correct Subsequence: "cng"

c n g
1 5 6 (sequential order)

Incorrect Subsequence: "dcn"

d n c
3 5 1 (not sequential order)

Although the characters in the incorrect subsequence are all found within the original string, the order in which they are arranged must be in the same relative order as the original sequence of characters.

For a sequence of size n, we can have a total of 2n - 1 non-empty subsequences.

Dynamic Programming

Refer to the Prerequisite Knowledge section in Coin Change 2:

Coin Change 2

Algorithm

Two-Pointer Approach

In this approach, we use two pointers to compare the characters in both strings at the same time, while maintaining the relative order of the characters. If the number of same characters is equal to the smaller string, then we can conclude that the smaller string is a subsequence of the larger string.

1. Iterate through each string.

2. Check if the characters from each string are equal.

   a. If the characters are equal, increment the pointer of the first string.

   b. If the characters are not equal, increment the pointer of the second string.

3. Check if the value of the first pointer is equal to the length of the first string when the loop exits.

   a. If the values are equal, return true.

   b. If the values are unequal, return false.

Top-Down DP Approach

In this approach, we use a helper function to find the longest common subsequence (LCS) between the two given strings by building a top-down DP table, which returns the length of the LCS. In the function provided in the IDE to check if the smaller string is a subsequence of the larger string, we compare the length of the smaller string with the value returned by the helper function.

Longest Common Subsequence Algorithm

1. Initialize a two-dimensional array (m x n) to build the DP table.

2. Build the table by checking the following conditions:

   a. If the cell is in the first row or first column (i = 0 or j = 0), then initialize the value of the cell as 0.

   b. If the characters being compared in each string are equal, the value of the cell is obtained by incrementing the value of the solution in the top-left diagonal cell by 1.

   c. If the characters being compared in each string are unequal, the value of the cell is obtained by finding the maximum value between the value in the top cell and the left cell.

3. Return the value of the last cell in the table.

Subsequence Checking Algorithm

1. Store the length of the smaller string in a variable.

2. Call the helper function and check if the resulting value is equal to the length of the smaller string.

   a. If the values are equal, return true.

   b. If the values are unequal, return false.

Code

Solution 1

Two-Pointer Approach

bool isSubsequence(string s, string t) {
    int s_len = s.length(), t_len = t.length();
    int i = 0, j = 0;
    // Iterate through each string
    while(i < s_len && j < t_len) {
        // Increment i if a charcter is equal
        if(s[i] == t[j]) {
            i++;
        }
        // Increment j if a character is not equal
        j++;
    }
    // Check if the length of string s is equal to i
    return i == s_len ? true : false;
}

Solution 2

Dynamic Programming Approach

int lcs(string s, string t) {
    int m = s.length() + 1;
    int n = t.length() + 1;
    // Initialize a two-dimensional array of size m x n to build the DP table
    int dp[m][n];
    // Iterate through each row and column
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            // Initialize the first row and column as 0
            if(i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            // If the characters are equal, add one to the solution in the top left diagonal cell
            else if(s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // If the characters are not equal, find the maximum of the values of the top and left solutions
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // Return the value of the last cell in the table
    return dp[m - 1][n - 1];
}
bool isSubsequence(string s, string t) {
    int len = lcs(s, t);
    // Check if the length of the longest common subsequence is equal to the smaller string
    if(len == s.length()) {
        return true;
    }
    return false;
}