---
# System prepended metadata

title: LC 392. Is Subsequence
tags: [easy, leedcode, Sliding Window, DP, LCS, python, c++]

---

# 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<sup>4</sup></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<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub></code> where <code>k >= 10<sup>9</sup></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
```python=
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
```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++
```cpp=
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
