# LC 392. Is Subsequence

### [Problem link](https://leetcode.com/problems/is-subsequence/)

###### tags: `leedcode` `python` `c++` `easy` `DP` `LCS` `Sliding Window`

Given two strings <code>s</code> and <code>t</code>, return <code>true</code> if <code>s</code> is a **subsequence** of <code>t</code>, or <code>false</code> otherwise.

A **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., <code>"ace"</code> is a subsequence of <code>"abcde"</code> while <code>"aec"</code> is not).

**Example 1:**

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

**Example 2:**

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

**Constraints:**

- <code>0 <= s.length <= 100</code>
- <code>0 <= t.length <= 10⁴</code>
- <code>s</code> and <code>t</code> consist only of lowercase English letters.

**Follow up:** Suppose there are lots of incoming <code>s</code>, say <code>s₁, s₂, ..., s_k</code> where <code>k >= 10⁹</code>, and you want to check one by one to see if <code>t</code> has its subsequence. In this scenario, how would you change your code?

## Solution 1 - DP

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[-1][-1] == m

## Solution 2 - Sliding Window
#### Python

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        p1, p2 = 0, 0

        while p1 < m and p2 < n:
            if s[p1] == t[p2]:
                p1 += 1
            p2 += 1

        return p1 == m

#### C++

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int p1 = 0;
        int p2 = 0;

        while (p1 != s.size() && p2 != t.size()) {
            if (s[p1] == t[p2]) {
                p1++;
            }
            p2++;
        }

        return p1 == s.size();
    }
};

>### Complexity
>m = len(s)
>n = len(t)
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(mn) |
>| Solution 2 | O(m + n) | O(1) |

## Note
x