Subsequences (two-pointer test, exponential gen)

Subsequences keep relative order but may drop characters—testing if t is a subsequence of s uses two pointers in O(n). Generating all subsequences is exponential—use only for small n or implicit DP over bitmask states.

Why this shows up in the real world

Diff and merge tools reason about ordered edits as subsequence-like alignments. Streaming filters pass only rising timestamps—a monotone subsequence idea.

Core idea (explained for students)

Is subsequence: it = iter(s); return all(c in it for c in t) is clever but two-index loop is clearer. Count distinct subsequences moves to DP with modulo.

Try this in Python

def is_subsequence(s: str, t: str) -> bool:
    i = 0
    for c in s:
        if i < len(t) and c == t[i]:
            i += 1
    return i == len(t)


print(is_subsequence("abcde", "ace"))

Common mistakes

• Substring vs subsequence—substring must be contiguous.
• Greedy subsequence matching fails for some counting variants—read problem carefully.

Key takeaways

• Master the linear two-pointer subsequence test cold.
• For generation, prune with constraints early to cut search trees.