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.

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

• Invariant: s[:i] has been matched in order within t[:j].
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

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).

Complexity

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

Implementation notes (Go)

• Comparing bytes is fine for ASCII inputs.