# Nhut Nguyen # 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)`.

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