392 - Is Subsequence

Difficulty: Easy | Pattern: Two Pointers | Company tags: Google, Amazon, Snapchat

Problem Statement

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input: s = "ace", t = "abcde"
Output: true
Explanation: a[b]c[d]e → "ace" using indices 0, 2, 4

Example 2:

Input: s = "aec", t = "abcde"
Output: false
Explanation: 'e' appears after 'c' in t, but "aec" needs 'e' before 'c'

Constraints: 0 <= s.length <= 100; 0 <= t.length <= 10^4; both consist of lowercase letters.

Approach: Two Pointers — O(n) time, O(1) space

Key insight: Walk through t with pointer j. For each character in s, advance j until we find a match. If we match all characters of s, it's a subsequence.

def isSubsequence(s: str, t: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Algorithm Flow

Dry Run

s = "ace", t = "abcde"

i	j	s[i]	t[j]	Match?	i after
0	0	a	a	Yes	1
1	1	c	b	No	1
1	2	c	c	Yes	2
2	3	e	d	No	2
2	4	e	e	Yes	3
3	5	—	—	—	—

i = 3 == len(s) = 3 → True ✓

Follow-Up: Many Subsequences to Check (Binary Search)

If you need to check thousands of different s strings against the same t:

Preprocess t: For each character at each position, store the positions where that character appears. Then use binary search to quickly find the next position.

from bisect import bisect_left
from collections import defaultdict

def isSubsequence_bulk(s, t):
    # Preprocess t
    positions = defaultdict(list)
    for i, c in enumerate(t):
        positions[c].append(i)
    
    curr_pos = -1
    for c in s:
        locs = positions[c]
        idx = bisect_left(locs, curr_pos + 1)
        if idx == len(locs):
            return False
        curr_pos = locs[idx]
    return True

Edge Cases

• s = "" → always True (empty string is a subsequence of everything)
• s longer than t → always False
• s == t → True
• s has characters not in t → False

Complexity

Approach	Time	Space
Two pointers	O(n) where n = len(t)	O(1)
Binary search (bulk)	O(m log n) preprocessing per query	O(n) for index

Key Terms

Term	Definition
Two pointers	Using two indices (one per string) that only move forward, avoiding backtracking or extra space.
Subsequence	A sequence derivable from another by deleting zero or more elements without changing the relative order of the rest.
Greedy matching	Advancing the s pointer as soon as a match is found, since matching earlier never hurts future matches.
Binary search on positions	Preprocessing t into per-character sorted position lists, then binary searching for the next valid position — used for the bulk follow-up.

FAQ

Q: Can this be solved without extra space? A: Yes — the two-pointer approach uses O(1) extra space beyond the input strings.

Q: What if s is empty? A: Return True immediately; an empty string is trivially a subsequence of any string.

Q: What if s is longer than t? A: It can never be a subsequence, so the two-pointer scan will naturally end with i < len(s), returning False (an early length check can short-circuit this).

Q: How would this change if you needed to check thousands of different s strings against the same t? A: Preprocess t once into per-character position lists, then binary search each character of s against those lists (see Follow-Up section) — this amortizes preprocessing across many queries instead of re-scanning t each time.

Q: Why is the greedy "match as early as possible" strategy correct? A: Matching a character at the earliest available position in t never reduces the options for matching the rest of s, since any later match position is also available afterward — it's a classic exchange argument.

Quick Revision

• Goal: determine if s can be formed by deleting characters from t while preserving order.
• Two-pointer approach: advance j through t, advance i through s only on a match.
• Return True if i reaches len(s) — meaning every character of s was matched in order.
• Time: O(len(t)); Space: O(1).
• For repeated queries against the same t, preprocess character positions and use binary search instead — O(m log n) per query.
• Edge cases: empty s → True; s longer than t → False; s == t → True.
• Greedy earliest-match strategy is provably optimal (exchange argument).

Related Problems

• Longest Common Subsequence — related subsequence concept but requires DP instead of a greedy two-pointer scan.
• Number of Matching Subsequences — the bulk/binary-search follow-up generalized to counting many words against one string.
• 242 - Valid Anagram — another string-comparison problem, though solved with counting rather than pointers.