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.