Is Subsequence: Forward Two Pointers in Their Purest Form
The forward two-pointer solution to Is Subsequence, explained step by step — greedy intuition, JavaScript code, a worked walkthrough, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Is Subsequence looks almost too small to bother with — two strings, one yes/no answer. But it's the cleanest expression of a pattern you'll reuse constantly: forward two pointers, where two indices walk the same direction at different speeds. No converging ends, no window to shrink, no hash map. Just two cursors and one rule.
It's also a quiet lesson in greedy reasoning: the solution takes the first match it finds and never looks back, and that choice is provably always safe. The why is worth more than the code — the same argument justifies harder greedy solutions later.
The problem
Given two strings s and t, return true if s is a subsequence of t, otherwise false. A subsequence keeps relative order while allowing skipped characters — you can delete characters from t, but never rearrange them.
Input: s = "abc", t = "ahbgdc"
Output: true // a..b..c appear in this order inside "ahbgdc"
Input: s = "axc", t = "ahbgdc"
Output: false // there is no 'x' anywhere in tTwo constraint details matter: s is short (up to 100 characters) but t can be 10⁴ characters, so anything worse than one pass over t starts to hurt. And the official follow-up asks what happens when billions of different s strings arrive against the same t — hold that thought, it changes the answer.
The word subsequence is doing precise work: "ace" is a subsequence of "abcde" (skip b and d) but not a substring, because substrings must be contiguous. Mixing those up is the fastest way to solve the wrong problem.
The brute force baseline
The first version most people write is recursive: compare the heads of both strings, consume accordingly, recurse on the rest.
function isSubsequence(s, t) {
if (s.length === 0) return true; // matched everything
if (t.length === 0) return false; // ran out of source
if (s[0] === t[0]) {
return isSubsequence(s.slice(1), t.slice(1)); // consume both
}
return isSubsequence(s, t.slice(1)); // skip one char of t
}The logic is correct — the cost is not. Every call builds brand-new strings with .slice(1), and slicing is O(length). With t at 10⁴ characters you make up to 10⁴ recursive calls, each copying up to 10⁴ characters: roughly O(n²) work for what is fundamentally a linear scan. And the call stack grows as deep as t is long — a real stack-overflow risk.
The recursion is telling you something, though. It only ever moves forward — nothing backtracks, nothing branches. When a recursion has exactly one path through it, it's an iteration wearing a costume.
The key insight: two pointers, one rule
Replace the recursion with two indices and let each one own a job:
iwalkss— the slow pointer. It advances only when its character is found.jwalkst— the fast pointer. It advances every single iteration, match or not.
The entire algorithm is one rule: advance i only on a match; j keeps moving regardless. When the loop ends, i reaching the end of s means every character was found in order; anything less means t ran out first.
The hidden question is why taking the first available match is safe. Suppose s[i] matches at position j, but you skip it hoping for a "better" match later at j' > j. Everything matchable after j' was already matchable after j — a later starting point can only shrink your options, never grow them. So the earliest match is always at least as good as any alternative. That's an exchange argument, and it's the entire greedy proof.
The optimal solution
function isSubsequence(s, t) {
let i = 0;
let j = 0;
while (i < s.length && j < t.length) {
if (s[i] === t[j]) {
i++;
}
j++;
}
return i === s.length;
}Notice the asymmetry: i++ lives inside the if, j++ lives outside it. That placement is the whole algorithm. On a match, both pointers move; on a mismatch, only j does — the character t[j] is simply skipped, which is exactly what "subsequence" permits.
The final line is the other subtle choice: return i === s.length, not anything about j. The question was never "did we finish scanning t?" — it was "did we find all of s?". As a bonus, an empty s never enters the loop and correctly returns true with zero special-casing.
Walkthrough: s = "abc", t = "ahbgdc"
| Step | i | j | s[i] | t[j] | Match? | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | a | a | yes | i → 1, j → 1 |
| 2 | 1 | 1 | b | h | no | skip, j → 2 |
| 3 | 1 | 2 | b | b | yes | i → 2, j → 3 |
| 4 | 2 | 3 | c | g | no | skip, j → 4 |
| 5 | 2 | 4 | c | d | no | skip, j → 5 |
| 6 | 2 | 5 | c | c | yes | i → 3, j → 6 |
| 7 | 3 | 6 | — | — | loop exits | i === 3 === s.length → true |
Watch how i gets stuck at 2 for three iterations while j marches past g and d hunting for a c. That stall-and-catch-up rhythm is the signature of the pattern. Run the failing case s = "axc" and the opposite happens: i stalls at 1 forever because no x exists, j exhausts t, and 1 !== 3 returns false. Step through both interactively to watch the pointers move character by character.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Recursion with slicing | O(n²) | O(n) | each call copies the remaining strings; stack as deep as t |
| Forward two pointers | O(n) | O(1) | one pass over t; two integer indices, no allocation |
| Index buckets + binary search | O(m log n) per query | O(n) | the follow-up: preprocess t once, answer many s queries |
Here n = t.length and m = s.length. Both pointers only ever move forward, so total pointer movement — and total work — is bounded by n + m. The last row matters only when the same t faces a stream of queries; for a single check, two pointers is optimal.
Common mistakes
- Advancing
jonly on a mismatch.jmust move every iteration. If you putj++inside anelse, a match freezesjand you'll re-compare the samet[j]against the nexts[i]— matching one source character twice. - Returning
j === t.lengthinstead ofi === s.length. Finishing the scan oftproves nothing;s = "abc",t = "ab"finishestand is stillfalse. Success is defined entirely byi. - Solving substring instead of subsequence. If you find yourself resetting
iback to 0 after a mismatch, you've drifted into substring matching, which requires contiguity. In a subsequence check,inever moves backward. - Using
t.indexOf(s[i])from position 0 each time. Restarting from the front can find characters out of order — fors = "ba",t = "ab", naive indexOf finds both letters and wrongly says yes. Search only forward from the previous match. - Special-casing the empty string unnecessarily.
s = ""is a subsequence of everything, and the code already returnstruefor it. Extra guards just add surface area for bugs.
Where this pattern shows up next
Forward two pointers is one of three two-pointer configurations, and the others are worth learning as deliberate contrasts:
- Two Sum II - Input Array Is Sorted — the converging configuration: pointers start at opposite ends and squeeze inward, powered by sorted order.
- Container With Most Water — converging pointers plus a greedy exchange argument that echoes the one you just used here.
- Find the Index of the First Occurrence in a String — the substring cousin, where contiguity forces a completely different (resettable) matching strategy.
- Two Sum — the unsorted pair problem where pointers don't help at all and a hash map takes over; knowing when the pattern doesn't apply is half the skill.
FAQ
What is the difference between a subsequence and a substring?
A substring must be contiguous — its characters sit next to each other in the original string. A subsequence only preserves relative order and may skip characters. "ace" is a subsequence of "abcde" but not a substring; "bcd" is both. Is Subsequence permits skips, which is exactly why the algorithm can discard non-matching characters of t and keep going instead of restarting.
Why does the greedy first-match approach always work?
Because taking an earlier match never reduces your future options. If s[i] matches t at position j and you instead wait for a later occurrence at j' > j, every character available after j' was already available after j — plus more. So the greedy scan finds a valid alignment whenever one exists. This exchange argument is the standard way to prove greedy algorithms correct.
What is the time complexity of Is Subsequence?
O(n) time and O(1) space, where n is the length of t. Both pointers only move forward: j advances once per iteration and i at most once per match, so the loop runs at most n times with constant work each. No auxiliary data structures are needed — just two integer indices.
How do you handle the follow-up with billions of query strings s?
Preprocess t once instead of rescanning it per query. Build a map from each character to the sorted list of positions where it appears in t (index buckets). For each query, walk s and binary-search each character's bucket for the first position strictly after the previous match. A query of length m then costs O(m log n) instead of O(n) — a massive win when queries number in the billions.
Is an empty string a subsequence of any string?
Yes. An empty s has zero characters to match, so the condition is vacuously satisfied — even against an empty t. The two-pointer code handles this without any special case: the loop never executes, i stays at 0, and 0 === s.length returns true.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.