Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Walk a pointer through `t`; every time the current `t` character matches the next needed `s` character, advance the `s` pointer. `s` is a subsequence iff its pointer reaches the end. O(n) time, O(1) space. For the follow-up (many `s` queries against one fixed `t`), preprocess `t` into per-character sorted index lists and binary-search each query.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize order-preserving membership as a one-pass two-pointer greedy, and whether you can extend it efficiently to the 'many queries, fixed t' follow-up.
Where candidates slip
Confusing subsequence with substring (requiring contiguity), or advancing the s pointer even on a mismatch. For the follow-up, re-scanning t per query instead of preprocessing it once.
How to stand out
Nail the two-pointer in O(n), then proactively raise the follow-up: 'if there are many s queries against one t, I'd preprocess t into per-character sorted index lists and binary-search, or build a next-position DP table.'
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewi = 0 (into s)i < len(s) and s[i] == c?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Two Pointers — Greedy Linear Scan (Optimal)
1Hint 1Explore hintHide hint
You need the characters of s to appear in t in order. If you scan t once, what should you do each time you see the next character of s you're looking for?
2Hint 2Explore hintHide hint
Keep an index i into s. Walk t left to right; whenever t's current character equals s[i], move i forward — you've matched that character of s.
3Hint 3Explore hintHide hint
If i reaches len(s), every character of s was matched in order → true. If t runs out first, → false.
A · Core idea
Subsequence membership is the archetypal two-pointer greedy. We keep a pointer i marking the next character of s we still need to find, and we sweep a pointer through t. Each time t's current character equals s[i], we've satisfied that character of s, so we advance i. When the sweep ends, s is a subsequence exactly when i has reached len(s) — meaning every character of s found a home in t, in order.
Why we only advance `i` on a match. The defining property of a subsequence is order preservation. The i pointer must move strictly forward through s and only when the current t character is the one s needs next. We never rewind i, because a subsequence can't reuse or reorder characters. Meanwhile the t pointer always advances — a non-matching t character is simply a 'deletion' we skip over, which is allowed.
Why greedy (earliest match) is provably correct. A natural worry: by grabbing the first occurrence of s[i] in t, could we accidentally consume a character we'd have needed later, blocking a valid match? No — and the exchange argument is clean. Suppose some valid matching pairs s[i] with a later position p in t. Taking the earliest position q ≤ p instead leaves the suffix t[q+1:] ⊇ t[p+1:], so anything the later choice could still match, the earlier choice can match too. Earliest-match never reduces future options, so greedy is safe. This is why we don't need backtracking or DP for a single query.
Why the empty-`s` and exhausted-`t` cases just work. If s is empty, i starts at 0 == len(s) and the final check returns true without matching anything — correct, since the empty string is everyone's subsequence. If t is exhausted before i reaches the end, the loop stops and i < len(s) yields false. The i < len(s) guard inside the loop also prevents indexing past the end of s once we've already matched all of it.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "abc", t = "ahbgdc"Interactive diagram
Greedy earliest-match leaves the most of t
t='a'Matching s[i] at the earliest spot keeps the largest suffix of t for later characters.
trueC · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Order-preserving membership = scan the long string once, consume the short string greedily. The earliest-match exchange argument is the proof that greedy beats DP here for a single query — worth stating to show you know why it's correct, not just that it works.
ComplexityO(n) time, O(1) space — A single pass over t (length n), with the s pointer advancing at most |s| times → O(n) time. Only two integer pointers are used → O(1) extra space.
E · Edge cases and pitfalls8s = "", t = "abc" — Loop never needs to match; i stays 0 == len(s) → true.Explore edge casesHide edge cases
Edge cases handled
s = "", t = "abc"Loop never needs to match; i stays 0 == len(s) → true.s = "abc", t = ""Loop body never runs; i = 0 != 3 → false.s = "aaaa", t = "aa"Only two a's available; i reaches 2, not 4 → false.s = t = "abc"Every char matches in order → true.
Pitfalls
- Treating it as substring (requiring contiguity) — subsequence allows gaps.
- Advancing the s pointer on a mismatch — corrupts the order check.
- Indexing s[i] without the i < len(s) guard after s is fully matched.
- Returning at the first match instead of checking i reached the end.
Approach 2 of 2
Preprocess t — Index Lists + Binary Search (Follow-up: Many Queries)
1Hint 1Explore hintHide hint
If t is fixed and you'll test thousands of s strings, re-scanning all of t per query is wasteful. What could you compute about t ONCE to speed up each query?
2Hint 2Explore hintHide hint
For each character, store the sorted list of indices where it appears in t. Then matching s greedily becomes: 'find the smallest index of s[i] in t that is strictly greater than where I matched the previous character.'
3Hint 3Explore hintHide hint
That 'smallest index greater than prev' is an upper-bound binary search on the character's index list. If any character has no such index, s isn't a subsequence.
A · Core idea
The follow-up changes the economics: with k ≥ 10⁹ queries against a single fixed t, the O(|t|) per-query scan from the two-pointer approach becomes the bottleneck. The fix is to pay an O(|t|) preprocessing cost once and make each query sublinear in |t|.
The preprocessing. Scan t once and, for each character, record the sorted list of positions where it occurs. For t = "abcabc", we'd store a → [0, 3], b → [1, 4], c → [2, 5]. Because we append while scanning left to right, each list is automatically sorted ascending.
Answering a query with binary search. We track prev, the index in t where we matched the previous character of s (initially -1). For each character c of the query, we need the smallest position of c in t that is strictly greater than prev — that's an upper-bound (bisect_right) search on c's index list. If c never appears, or every occurrence is ≤ prev, the search falls off the end and s is not a subsequence. Otherwise we set prev to that position and continue. This mirrors the greedy earliest-match logic of the two-pointer version, but jumps directly to the next valid position instead of scanning over the gaps.
Why this is the right amortization. Preprocessing is O(|t|) once. Then each query costs O(|s| · log|t|) — for short s (≤ 100 here) that's tiny, and crucially independent of how much of t lies between matches. Over k queries the total is O(|t| + Σ|s_i|·log|t|), vastly better than O(k·|t|).
The DP alternative — next-position table. Because the alphabet is a fixed 26 letters, an even slicker preprocessing is a next-position DP table: nxt[i][c] = the smallest index ≥ i in t where character c occurs (or a sentinel if none). Build it right-to-left in O(|t|·26). Each query then becomes a pure O(|s|) walk: from position pos, jump to nxt[pos][s[k]] + 1, with no binary search at all. This is the dynamic-programming framing of the same idea and is often the cleanest answer to give for the follow-up when the alphabet is small and fixed.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
t = "ahbgdc" preprocessed; query s = "abc"c='a'
a→[0]; first index > -1 is 0
prev = 0trueC · Code with teaching comments
Reference implementation previewpublic boolean isSubsequence(String s, String t) { Map<Character, List<Integer>> idx = new HashMap<>(); for (int i = 0; i < t.length(); i++) { idx.computeIfAbsent(t.charAt(i), k -> new ArrayList<>()).add(i); }Explore the full codeHide the full code
D · Why it works and complexityO(|t|) preprocess, then O(|s|·log|t|) per query timeO(|t|) spaceOpen the invariant and proofExplore the proofHide the proof
When one structure (t) is queried many times, shift work from per-query to one-time preprocessing. Index-lists-plus-binary-search and the 26-column next-position DP table are two encodings of the same 'jump to the next occurrence' idea — the latter trades a little build cost for O(|s|) queries with no logs.
ComplexityO(|t|) preprocess, then O(|s|·log|t|) per query time, O(|t|) space — Building char → sorted index lists is one pass over t → O(|t|) time and space. Each query does, per character of s, one binary search over that character's index list → O(|s|·log|t|). Across many queries the O(|t|) build is amortized away.
E · Edge cases and pitfalls7query char absent from t — idx.get(c) is None/null → immediately false.Explore edge casesHide edge cases
Edge cases handled
query char absent from tidx.get(c) is None/null → immediately false.s = ""No characters to match → loop skipped → true.repeated chars in s like "aa"Second 'a' must be found strictly after the first via upper bound — correctly fails if only one 'a' exists.
Pitfalls
- Using lower bound instead of upper bound — could re-match the same position (allows reuse, wrong).
- Rebuilding the index structure per query — defeats the entire point of the follow-up.
- Forgetting the 'character absent' case → null/KeyError.
- For the DP table variant, off-by-one in the sentinel for 'no next occurrence'.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean isSubsequence(String s, String t) { int i = 0; for (int j = 0; j < t.length() && i < s.length(); j++) { if (s.charAt(i) == t.charAt(j)) { i++;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Advancing the s pointer on a mismatch
Moving i when characters differ breaks the order-preserving match and can wrongly accept or reject; i must move only on a match.
Explore the code comparisonHide the code comparison
Advancing the s pointer on a mismatch
Moving i when characters differ breaks the order-preserving match and can wrongly accept or reject; i must move only on a match.
Don't write this
i = 0
for c in t:
if i < len(s):
i += 1 # wrong: advances even on mismatch
return i == len(s)Write this instead
i = 0
for c in t:
if i < len(s) and s[i] == c:
i += 1 # advance only on a match
return i == len(s)2Treating it like a substring search
Subsequence allows skipping characters in t. Requiring a contiguous block (e.g. t.contains(s)) rejects valid cases like s='ace', t='abcde'.
Explore the code comparisonHide the code comparison
Treating it like a substring search
Subsequence allows skipping characters in t. Requiring a contiguous block (e.g. t.contains(s)) rejects valid cases like s='ace', t='abcde'.
Don't write this
return t.contains(s); // wrong: demands a contiguous substringWrite this instead
int i = 0;
for (int j = 0; j < t.length() && i < s.length(); j++)
if (s.charAt(i) == t.charAt(j)) i++;
return i == s.length();3Re-scanning t per query (follow-up)
With k ≥ 10⁹ queries, an O(|t|) scan each time is O(k·|t|). Preprocess t once into index lists and binary-search per query instead.
Explore the code comparisonHide the code comparison
Re-scanning t per query (follow-up)
With k ≥ 10⁹ queries, an O(|t|) scan each time is O(k·|t|). Preprocess t once into index lists and binary-search per query instead.
Don't write this
def query(s, t):
# O(|t|) every call, ignoring that t is fixed
i = 0
for c in t:
if i < len(s) and s[i] == c: i += 1
return i == len(s)Write this instead
# build idx = char -> sorted positions ONCE for fixed t,
# then each query is O(|s| log |t|) via bisect (see optimal approach)Revise
Carry the pattern into the interview
Pattern to remember
Two pointers (greedy left-to-right match)
Code pattern to memorize
i = 0
for c in t:
if i < len(s) and s[i] == c: i += 1
return i == len(s)Rules to remember
- 1Advance the `s` pointer only on a match; always advance through
t. Order withinsmust be preserved, so greedy first-match is safe. - 2`s` is a subsequence iff its pointer reaches `len(s)` — i.e. every character of
swas matched in order. - 3Greedy is provably correct: taking the earliest matching position in
tnever blocks a later match (it leaves the most oftavailable). - 4Empty `s` is trivially a subsequence of any
t— the loop matches zero characters andi == 0 == len(s). - 5For many queries on the same `t`, preprocess once into char → sorted indices and binary-search, turning each query into
O(|s|·log|t|).
Use this pattern when
- Check whether one sequence appears in another while preserving relative order (not contiguity)
- Single linear pass suffices and order matters but gaps are allowed
- Greedy earliest-match reasoning applies (subsequence membership)
- Many queries against a fixed text → preprocess once, answer each fast
Choose another pattern when
- You need a CONTIGUOUS match (substring) → that's strStr/KMP, not subsequence
- You need the LONGEST common subsequence of two strings → LCS dynamic programming
- You need to count distinct subsequences → counting DP, not a membership check
- Characters can be reordered freely → that's an anagram/multiset question
Interview takeaway
Subsequence membership is the textbook two-pointer greedy: scan the haystack `t`, consume `s` in order, and you're done in O(n). The interview depth lives in the follow-up — when `t` is fixed and you face many `s` queries, amortize by preprocessing `t` into index lists (binary search) or a next-position DP table.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternTwo-pointer greedy for order-preserving membership: scan t once, consume s on matches, O(n). The follow-up (many queries on a fixed t) is the real interview depth — preprocess t into per-character sorted index lists (binary search) or a 26-column next-position DP table to make each query sublinear in |t|. Related: Number of Matching Subsequences and Longest Common Subsequence.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Longest Common SubsequenceComing soonWhen you need the longest shared subsequence (not just membership), two pointers no longer suffice — use 2D DP.
- Number of Matching SubsequencesComing soonExactly the many-queries follow-up: bucket words by their next-needed char or preprocess t and answer each.
- Distinct SubsequencesComing soonCount how many ways s appears as a subsequence of t — counting DP, a step beyond membership.