Is Subsequence

First Unique Character in a String

Majority Element

Check whether one string is a subsequence of another.

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. For example, `"ace"` is a subsequence of `"abcde"` while `"aec"` is not.

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

**Constraints**
- `0 <= s.length <= 100`
- `0 <= t.length <= 10^4`
- `s` and `t` consist only of lowercase English letters.

**Follow-up**
If there were a huge number of incoming `s` strings to check against the same `t`, say millions, how would you change your algorithm to answer each query efficiently?

- `s` is a subsequence of `t` if all characters of `s` appear in `t` in the same order.
- Characters in `t` may be skipped, but characters in `s` cannot be reordered.
- An empty `s` is always a subsequence.

Understand What Subsequence Means

- We do not need to generate all possible subsequences of `t`.
- Instead, scan `t` from left to right and try to match the next needed character from `s`.
- If every character from `s` is matched, return `True`.

Think About a Direct Scan

- Pointer `i` tracks the next character needed from `s`.
- Pointer `j` is the current position while scanning `t`.
- When `s[i] == t[j]`, advance `i`; always continue scanning through `t`.

Use Two Pointers

- Once `i` reaches `len(s)`, every character in `s` has been matched.
- At that point we can return `True` without scanning the rest of `t`.
- If the scan ends first, return whether all of `s` was matched.

Handle Completion Early

- The scan preserves order because `t` is processed left to right exactly once.
- Time complexity is O(len(t)) and space complexity is O(1).
- The empty string case works naturally because `i == len(s)` at the start.