# Problem statement

Given two strings `s`

and `t`

, return `true`

if `s`

is a subsequence of `t`

, or `false`

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., `"ace"`

is a subsequence of `"abcde"`

while `"aec"`

is not).

## Example 1

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

## Example 2

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

## Constraints

`0 <= s.length <= 100`

.`0 <= t.length <= 10^4`

.`s`

and`t`

consist only of lowercase English letters.

**Follow up**: Suppose there are lots of incoming `s`

, say `s1`

, `s2`

, ..., `sk`

where `k >= 10^9`

, and you want to check one by one to see if `t`

has its subsequence. In this scenario, how would you change your code?

# Solution

For each character of `s`

, find if it exists in `t`

. If not, return `false`

.

Otherwise, continue with the next character of `s`

and the finding starting from the position after the last found one.

## Code

```
#include <iostream>
using namespace std;
bool isSubsequence(string s, string t) {
int i = -1;
for (char c : s) {
i++;
while (i < t.length() && t[i] != c) {
i++;
}
if (i >= t.length()){
return false;
}
}
return true;
}
int main() {
cout << isSubsequence("abc", "ahbgdc") << endl;
cout << isSubsequence("axc", "ahbgdc") << endl;
cout << isSubsequence("aaaa", "bbaaa") << endl;
}
```

```
Output:
1
0
0
```

## Complexity

- Runtime:
`O(N)`

, where`N = t.length`

. - Extra space:
`O(1)`

.

# Follow up

Suppose there are lots of incoming `s`

, say `s1, s2, ..., sk`

.

- If some is a subsequence of
`t`

then return`true`

. - If none of them satisfies, return
`false`

.

## Code

```
#include <iostream>
#include <vector>
using namespace std;
bool isSubsequence(string s, string t) {
int i = -1;
for (char c : s) {
i++;
while (i < t.length() && t[i] != c) {
i++;
}
if (i >= t.length()){
return false;
}
}
return true;
}
bool hasSubsequence(vector<string>& strings, string t) {
for (string& s : strings) {
if (isSubsequence(s, t)) {
return true;
}
}
return false;
}
int main() {
vector<string> strings{"abc", "axc", "aaaa"};
cout << hasSubsequence(strings, "ahbgdc") << endl;
strings = {"abcd", "axc", "aaaa"};
cout << hasSubsequence(strings, "ahbgdc") << endl;
}
```

```
Output:
1
0
```

## Complexity

- Runtime:
`O(kN)`

, where`k = strings.length`

and`N = t.length`

. - Extra space:
`O(1)`

.

### Did you find this article valuable?

Support **Nhut Nguyen** by becoming a sponsor. Any amount is appreciated!