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(len(t)) scan answers one query; the follow-up wants each query in roughly O(len(s) · log len(t)) after preprocessing.

Think about it first

TL;DR

Greedy two-pointer scan — O(len(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).

def isSubsequence(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(len(t)) time and O(len(t)) stack depth — every call advances j by one, so there are at most len(t) frames. The stack depth is the problem: at len(t) = 10^4 it exceeds CPython’s default recursion limit of 1000, and raising the limit only trades the crash for slow, memory-heavy recursion. The logic is correct; the iterative form below avoids the deep stack.

Approach 2 — Greedy two pointers

When looking for the next character of s, taking its earliest occurrence in t is never worse: any later choice only leaves less of t for the remaining characters of s. This exchange argument makes the greedy rule (commit to each earliest match, never backtrack) correct, and turns the recursion into a single scan.

def isSubsequence(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(len(t)) time, O(1) space.

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

With billions of queries against one fixed t, re-scanning t for every query is wasteful. Preprocess t once into a map from each letter to the sorted list of its positions. Matching a query character after position p then becomes “first occurrence of this letter strictly after p”, which is a binary search over the sorted list via bisect_right.

from bisect import bisect_right
from collections import defaultdict


def isSubsequence(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(len(t)) preprocessing once, then O(len(s) · log len(t)) per query, O(len(t)) space for the map. For a single query the two-pointer scan wins; for k queries this turns O(k · len(t)) into O(len(t) + k · len(s) · log len(t)).

Doing the binary search by hand

bisect_right is convenient, but interviewers usually want to see you write the search yourself. The call bisect_right(occ, prev) is just “the first index k whose value is strictly greater than prev” — a plain binary search on the sorted occ:

def first_after(occ: list[int], prev: int) -> int:
    lo, hi = 0, len(occ)          # answer lies in the half-open range [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2      # // is integer division
        if occ[mid] <= prev:
            lo = mid + 1          # occ[mid] is too small; the answer is to its right
        else:
            hi = mid              # occ[mid] qualifies; keep it and look left for an earlier one
    return lo                     # equals bisect_right(occ, prev)

Then drop first_after into the loop in place of bisect_right:

from collections import defaultdict


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

    prev = -1
    for ch in s:
        occ = positions[ch]
        k = first_after(occ, prev)      # hand-rolled instead of bisect_right
        if k == len(occ):
            return False
        prev = occ[k]
    return True

Two details make it correct: starting hi at len(occ) (the half-open convention) is what lets “no occurrence after prev” fall out naturally as k == len(occ), and comparing with <= (not <) is what gives strictly after prev — the same distinction as bisect_right versus bisect_left.

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 problem to one forward scan with a single pointer. When the same sequence serves many queries, preprocess it once into a map from value to sorted positions, so each query resolves with logarithmic lookups instead of a full scan.