Is Subsequence

Given two strings s and t, return true if s is a subsequence of t. A subsequence keeps character order but not necessarily contiguity.

This can be solved with two pointers in a single pass over t.

Why this is worth learning

The earliest available match leaves the most remaining text for later characters. This exchange argument justifies advancing greedily rather than backtracking.

Before coding: one-minute experiment

For s="aa" and t="ab", why can the one a not satisfy both positions?

Function signature

func IsSubsequence(s string, t string) bool

Inputs / outputs

• s: candidate subsequence.
• t: target string.
• Return: true if s is a subsequence of t.

Example

s = "abc", t = "ahbgdc"
Output: true

Constraints

• 0 <= len(s), len(t) <= 200_000

Core idea (near-solution)

Use two pointers:

• i scans s.
• j scans t.

Invariant: s[:i] has been matched in order within t[:j].

Algorithm (step-by-step)

1. Initialize i = 0.
2. For each j from 0 to len(t)-1:
   • If i < len(s) and s[i] == t[j], increment i.
3. At the end, return i == len(s).

Correctness sketch

After scanning t[:j], i is the largest prefix length of s matchable within that scanned text, using the earliest possible positions. A nonmatching byte cannot extend that prefix. If t[j] equals s[i], taking it extends the prefix by one; no later choice could leave more room for the remaining suffix. Any other matching of the same prefix ends no earlier than this greedy one, by induction on the matched positions. Consequently, if greedy reaches len(s), it has constructed a subsequence; if it does not, no alternative matching could have completed it within t.

Trace (hand walkthrough)

Example input:
s = "abc", t = "ahbgdc"
Output: true

Walk:
- i=0 (a), j=0 (a) -> match, i=1, j=1
- j=1 (h) skip; j=2 (b) matches -> i=2, j=3
- j=3 (g) skip; j=4 (d) skip; j=5 (c) matches -> i=3 done

Pitfalls to avoid

• Treating an empty s as false (it is always a subsequence).
• Resetting i on mismatches (do not move backward).

Debugging lens

The two indices belong to different strings and need not meet. Test empty s, repeated desired bytes, and a late final match. Never reset the matched-prefix length after a mismatch.

Complexity

• Time: O(len(t))
• Extra space: O(1)

Implementation notes (Go)

• Comparing bytes is fine for ASCII inputs.

Contract precision

The supplied implementation compares bytes. ASCII inputs have the usual character interpretation; changing to rune indices would be a different contract.

Reconstruction checkpoint

For s="aa" and t="ab", why can the one a not satisfy both positions?

Return to Two Pointers · Module quiz