392. Is Subsequence

Quick Identifier

Topic: two-pointers
Pattern: ordered stream matching
Difficulty: Easy
Companies: Amazon, Google, Meta, Bloomberg, Microsoft
Frequency: High
LeetCode: 392
Hint: Only advance the pattern pointer when the stream character matches it.

Quick Sights

Time Complexity: O(|t|) for one query.
Space Complexity: O(1) for one query.
Core Mechanism: Scan t; advance through s only on a match. If all of s is matched, return true.

Concept Explanation

A subsequence preserves order but not contiguity, so there is no reason to backtrack.

The invariant is: s[0:matched] has already been found in the processed prefix of t. A new character from t either extends that matched prefix by one, or it is irrelevant forever.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Generating subsequences is exponential. Two pointers solve one query in linear time. For many queries against the same t, preprocess character positions and binary search.

Optimal Solution

JavaScript

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

Go

func isSubsequence(s string, t string) bool {
	matched := 0
	for i := 0; i < len(t) && matched < len(s); i++ {
		if t[i] == s[matched] {
			matched++
		}
	}
	return matched == len(s)
}