Is Subsequence

Problem

Given two strings s and t, return True if s is a subsequence of t, and False otherwise.

A subsequence keeps characters in their original relative order but may skip any number of characters. Formally, s is a subsequence of t if you can delete zero or more characters from t (without reordering the rest) and obtain s. The empty string is a subsequence of everything.

Follow-up: if a huge number of query strings s1, s2, ..., sk (say k >= 10^9) will each be tested against the same t, how would you preprocess t to answer each query fast?

Examples

• s = "abc", t = "ahbgdc" → True — take a (index 0), b (index 2), c (index 5), in order.
• s = "axc", t = "ahbgdc" → False — after matching a, no x appears anywhere later in t.
• s = "", t = "xyz" → True — the empty string is a subsequence of any string.

Constraints

• 0 <= len(s) <= 100
• 0 <= len(t) <= 10^4
• Both strings consist of lowercase English letters only.

A single O(|t|) scan answers one query; the follow-up wants each query in roughly O(|s| log |t|) after preprocessing.

Think about it first

TL;DR

Greedy two-pointer scan — O(|t|) time, O(1) space (plus an index-map + binary-search variant for the many-queries follow-up).

Approach 1 — Brute force (recursive matching)

At each pair of positions (i, j) — i into s, j into t — either the characters match and both advance, or t’s character is skipped. Recurse until s is exhausted (success) or t is exhausted (failure).

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        def match(i: int, j: int) -> bool:
            if i == len(s):
                return True
            if j == len(t):
                return False
            if s[i] == t[j]:
                return match(i + 1, j + 1)
            return match(i, j + 1)

        return match(0, 0)

Complexity: O(|t|) time — each call advances j, so there are at most |t| frames — but also O(|t|) stack depth. That is what kills it: at |t| = 10^4 this brushes against CPython’s default recursion limit (1000 by default, and even when raised, deep recursion is slow and fragile). The logic is right; the shape is wrong.

Approach 2 — Greedy two pointers

The insight: when looking for the next character of s, taking its earliest occurrence in t is never worse — any later choice only shrinks what remains of t for the rest of s. This exchange argument makes a simple greedy algorithm (commit to each locally-earliest match, never backtrack) correct, and it converts the recursion into a flat scan.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0  # next character of s still to match
        for ch in t:
            if i < len(s) and s[i] == ch:
                i += 1
        return i == len(s)

Walkthrough on s = "abc", t = "ahbgdc":

i == len(s) == 3 → True. On s = "axc" the pointer sticks at x forever and ends at 1 → False.

Complexity: O(|t|) time, O(1) space.

Approach 3 — Index map + binary search (the follow-up)

The insight: with billions of queries against one fixed t, re-scanning t per query is the waste. Preprocess t once into a map from each letter to the sorted list of its positions; then matching a query character after position p is “first occurrence of this letter strictly after p” — a binary search (O(log) lookup in a sorted list) via bisect_right.

from bisect import bisect_right
from collections import defaultdict


class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        positions: defaultdict[str, list[int]] = defaultdict(list)
        for idx, ch in enumerate(t):
            positions[ch].append(idx)

        prev = -1  # position in t of the last matched character
        for ch in s:
            occ = positions[ch]
            k = bisect_right(occ, prev)
            if k == len(occ):
                return False  # no occurrence of ch after prev
            prev = occ[k]
        return True

Walkthrough on s = "abc", t = "ahbgdc":

• Preprocessing: a → [0], h → [1], b → [2], g → [3], d → [4], c → [5].
• ch = 'a', prev = -1: first position in [0] after -1 is 0 → prev = 0.
• ch = 'b', prev = 0: first position in [2] after 0 is 2 → prev = 2.
• ch = 'c', prev = 2: first position in [5] after 2 is 5 → prev = 5. All matched → True.

For s = "axc": positions['x'] is empty, bisect_right returns 0 = its length → False.

Complexity: O(|t|) preprocessing once, then O(|s| log |t|) per query, O(|t|) space for the map. For a single query the two-pointer scan wins; for k queries this turns O(k · |t|) into O(|t| + k · |s| log |t|).

Common pitfalls

• Confusing subsequence with substring — characters need not be contiguous, only in order. "ace" is a subsequence of "abcde", not a substring.
• Forgetting the empty-s edge case: it must return True (the loop never advances i, and 0 == len(s) holds — but only if your final check is i == len(s), not i > 0).
• In the follow-up, using bisect_left(occ, prev) — that can re-use the same position as the previous match; you need strictly-after, i.e. bisect_right.
• Indexing s[i] without the i < len(s) guard once s is fully matched — the scan of t continues after the last match.

Pattern takeaway

Order-preserving matching against a fixed sequence is greedy-safe: always take the earliest usable occurrence, which reduces the whole problem to one forward scan with a single pointer. And when the same haystack serves many queries, invert it once into a value → sorted-positions hash map so each query walks its own needle with logarithmic lookups — the standard “preprocess the static side” move.