Is Subsequence

---

Problem Statement:

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

---

Let’s take a moment to understand what a subsequence is before we delve into the solution.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, {A, B, D} is a subsequence of sequence {A, B, C, D, E} obtained after removing {C} and {E}.

People are often confused between a subarray/substring and a subsequence. A subarray or substring will always be contiguous, but a subsequence need not be contiguous. That is, subsequences are not required to occupy consecutive positions within the original sequences. But we can say that both contiguous subsequences and subarrays are the same.

In other words, the subsequence is a generalization of a substring, or the substring is a refinement of the subsequence. For example, {A, C, E} is a subsequence of {A, B, C, D, E}, but not a substring, and {A, B, C} is both a subarray and a subsequence.

---

Approach: Two Pointers

1. Base Case 1: If the length of the string S is greater than T, return False.

2. Base Case 2: If the string S is empty, return True.

3. Declare two new variables i and j and initialize them to 0.

4. compare the characters at their current positions i and j. If they are equal, we move both pointers to the next position in their respective strings.

5. If they are not equal, we only move the pointer j to the next position in T.

6. We repeat this process until we reach the end of S or T.

// ES6 Arrow Function
const isSubsequence = (s, t) => {
    // base case
    if(s.length > t.length) return false;
    if(!s) return true;

    let i = 0, j = 0;

    while(i < s.length && j < t.length) {
        if(s[i] == t[j]) {
            i++;
            j++;
        } else {
            j++;
        }
    }

    return i === s.length;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

Approach 2: Two-Pointer with slight modification

// ES6 Arrow Function
const isSubsequence = (s, t) => {
    // base case
    if(s.length > t.length) return false;
    if(!s) return true;

    let i = 0; 
    for(let j = 0; j < t.length; j++) {
        if(s[i] == t[j]) i++;
    }

    return i === s.length;
}

Note: Time and Space Complexity remains the same.

---

I hope this article has provided you with valuable insights and helped you better understand the different approaches to solve this problem. Happy coding!

---

Problem - Leetcode 392

Subsequence definition reference — TechieDelight