Is Subsequence - Two Pointers, Order Kept

A subsequence keeps relative order. It is not a substring (substrings must be contiguous). “ace” is a subsequence of “abcde”; “aec” is not - the e would have to appear before the c.

The problem

Given strings s and t, return true if s is a subsequence of t.

s = "abc", t = "ahbgdc"  → true   // a…b…c appear in order
s = "axc", t = "ahbgdc"  → false  // no 'x'
s = "",    t = "ahbgdc"  → true   // empty is a subsequence of everything
s = "acb", t = "ahbgdc"  → false  // order broken (c before b in s, but b before c in t)

Diagram: walk t = a h b g d c; match a, b, c in order (gaps OK). Order break acb → false.

Approach 1: Nested restart scan

For each character of s, scan t from the last match position forward until you find it. Correct. Same asymptotic idea as two pointers, but the control flow is “search for next letter” instead of “walk once.”

function isSubsequenceBrute(s, t) {
  let from = 0;
  for (let i = 0; i < s.length; i++) {
    let found = -1;
    for (let j = from; j < t.length; j++) {
      if (t[j] === s[i]) { found = j; break; }
    }
    if (found === -1) return false;
    from = found + 1;
  }
  return true;
}

Approach 2: indexOf chain (same idea, library)

Replace the inner scan with t.indexOf(s[i], from). Algorithmically identical. In V8 the search is implemented in C++ - wall-clock often wins hard on long strings.

function isSubsequenceIndexOf(s, t) {
  let from = 0;
  for (let i = 0; i < s.length; i++) {
    const idx = t.indexOf(s[i], from);
    if (idx === -1) return false;
    from = idx + 1;
  }
  return true;
}

Approach 3: Two pointers - interview pattern

One pointer i into s, one j into t. Walk t left to right. When s[i] === t[j], advance i. At the end, succeed iff every character of s was matched.

function isSubsequence(s, t) {
  let i = 0;
  for (let j = 0; j < t.length && i < s.length; j++) {
    if (s[i] === t[j]) i++;
  }
  return i === s.length;
}

Invariant: after processing t[0..j], the first i characters of s have been matched in order. Time O(|t|), extra space O(1). Empty s → i starts at 0 and never needs to advance → true.

Benchmark - large t, honest constants (Node, 30-run median)

Haystack t = 500,000 letters a-y (no z). Mixed batch: 400 queries, |s|≈80 - 200 true subsequences + 200 forced-false (…+z). Hard-false: 50 queries that match deep into t then fail.

Approach	Mixed (400 q) median	Hard-false (50 q) median
Nested scan	488.091 ms	125.650 ms
indexOf chain	8.831 ms	1.840 ms
Two pointers (JS)	861.366 ms	215.784 ms

indexOf ≈ 97× faster than two-pointer JS on the mixed batch (861.366 / 8.831). Nested scan beat two-pointer JS by ~1.76× - both are O(|t|) per query; the tight inner loop vs the single for-loop is a constant-factor fight, not a complexity win.

Product claim for interviews: ship two pointers for the invariant and O(1) space. Know that a native indexOf chain is the same algorithm with a faster engine. Do not claim “two pointers is always the fastest wall-clock implementation.”

Same honesty family as Day 18 (bucket O(n) lost to sort) and Day 32 (Sets lost to brute on 9×9).

What breaks?

• Treating subsequence as substring - requiring contiguous matches rejects valid answers (“ace” in “abcde”).
• Resetting the t pointer on every letter of s - re-scanning from 0 can match out of order or double-count positions.
• Advancing i without advancing j past the match - reuse the same t character for two letters of s.
• Forgetting empty s - the correct answer is true; i === 0 === s.length immediately.
• Selling two-pointer JS as free speed - pattern clarity ≠ V8 C++ indexOf.

How it connects

• Day 11 (Two Sum): two ideas that “feel like two ends,” but Two Sum used a hash map; here both pointers move through strings with an order invariant.
• Day 19 (Product except self): directional accumulation - left-to-right commitment. Here the commitment is “how much of s is done.”
• Day 26 (sequence heads): one O(1) check decides whether to advance state.
• Day 18 / Day 32: Big-O honesty - interview pattern can lose wall-clock to a native primitive.
• Day 25 (encode/decode): order-sensitive string parsing; wrong pointer movement silently corrupts framing.

Quiz