> For the complete documentation index, see [llms.txt](https://twchen.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://twchen.gitbook.io/leetcode/dynamic-programming/is-subsequence.md).

# Is Subsequence

## Description

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

You may assume that there is only lower case English letters in both **s** and **t**. **t** is potentially a very long (length \~= 500,000) string, and **s**is a short string (<=100).

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).

**Example 1:**

```
s = "abc", t = "ahbgdc"
Return true.
```

**Example 2:**

```
s = "axc", t = "ahbgdc"
Return false.
```

**Follow up:**\
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

## Solutions

### For original

```cpp
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0;
        for(int j = 0; i < s.size() && j < t.size(); ++j){
            if(s[i] == t[j]){
                ++i;
            }
        }
        return i == s.size();
    }
};
```

### For follow-up

Store the indices of characters in `t` in a hash table `T`.

For each `s`, use the following algorithm check is `s` is a subsequence of `t`.

Let `i` be the index of the first unused character in `t`. Initially `i = 0`.

For each character `c` in `s`, find the first index of `c` in `t[i..]`. The indices of `c` are stored in `T[c]`  as a sorted list. We can use binary search to find the index in `O(t.size())` time. If no such index, return false. Otherwise set `i` to the index + 1.

Let `n` be the average length of `s`, `k` be the number of `s`, `m` be the length of `t`. Then the running time is `O(m + k * n * log(m))`. running time using the solution for the original problem is `O(k * m)`.

```cpp
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> hash(26);
        for(int i = 0; i < t.size(); ++i){
            hash[t[i] - 'a'].push_back(i);
        }
        return isSubsequence(s, hash);
    }
    
    bool isSubsequence(string &s, vector<vector<int>> &t){
        int i = 0;
        for(char c: s){
            auto indices = t[c - 'a'];
            auto it = lower_bound(indices.begin(), indices.end(), i);
            if(it == indices.end())
                return false;
            else
                i = *it + 1;
        }
        return true;
    }
};
```