519. Is It a Subsequence

Print yes if s is a subsequence of t, or no otherwise. A subsequence keeps the original order and may skip characters.

s = abc, t = ahbgdc -> yes s = axc, t = ahbgdc -> no s = ba, t = ab -> no order matters

This problem sits in a topic full of grids, and it needs none of them. Telling the two situations apart is the point.

## Why no table is needed

Walk t once, carrying a pointer into s. Whenever the current character of t equals the character s is waiting for, advance the pointer:

i = 0 for ch in t: if i < len(s) and ch == s[i]: i += 1 answer = (i == len(s))

## Why taking the first match is safe

The exchange argument. Suppose s is a subsequence of t using some set of positions, and let p be the first position that set uses for s[0]. The greedy takes the EARLIEST occurrence of s[0], at some position q <= p.

Every later position the witness uses is after p, hence after q, so swapping q in leaves a valid witness. Repeat on the remainder and the greedy's choices can replace an optimal witness step by step without ever failing.

So matching greedily is never worse, and the pointer never needs to back up.

That is exactly the property the grid problems in this topic do NOT have. In edit distance or longest common subsequence, taking an early match can be wrong, because a character may be better spent later. Here there is nothing to spend: a character of s either gets matched or the answer is no.

## The distinguishing question

Does an early choice ever cost something later? For plain containment the answer is no, so a single pass suffices. For anything where characters COMPETE, a pointer is not enough and the table earns its place.

## Boundaries

abcd against abc answers no: s longer than t can never be contained, and the loop handles it without a length check, since the pointer cannot reach the end.

a against a answers yes and a against b answers no.

aaa against aabaa answers yes, which checks that repeated characters advance the pointer one at a time rather than being matched as a group.

## Cost

Time O(|t|). Space O(1).

That is why the constraints here are large: a quadratic solution is ruled out by the bound, which is itself a hint that no table is intended.

Constraints - `1 ≤ length of s ≤ 200000` - `1 ≤ length of t ≤ 200000` - both contain only lowercase letters