Is Subsequence

Problem Statement

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

A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining ones.

Input:  s = "abc", t = "ahbgdc"
Output: true
Why:    a h b g d c
        ↑   ↑     ↑

Input:  s = "axc", t = "ahbgdc"
Output: false
Why:    'a' and 'c' appear, but there is no 'x'

Intuition

The greedy part is subtle but important: always match at the earliest opportunity. If s[i] can be matched now, matching it now is never worse than waiting for a later occurrence — an earlier match leaves strictly more of t available for the remaining characters.

Real-world analogy

Proofreading a long document for a checklist of words that must appear in order. You read the document once, top to bottom, ticking items off as you encounter them. You never go back — and you tick an item the first time you see it, because saving it for later can only cost you.

Watch it run

Approach

Solution

def is_subsequence(s: str, t: str) -> bool:
    """True if s can be formed by deleting characters from t."""
    i = 0   # index into s — the character we are looking for

    for char in t:
        if i < len(s) and s[i] == char:
            i += 1

    return i == len(s)

def is_subsequence_two_pointers(s: str, t: str) -> bool:
    i = j = 0

    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1

    return i == len(s)

The Follow-Up That Changes the Answer

LeetCode adds: what if there are billions of strings s₁, s₂, … to check against the same t?

The two-pointer solution costs O(|t|) per query, so a billion queries means a billion full scans of t.

t = "ahbgdc"
{a: [0], h: [1], b: [2], g: [3], d: [4], c: [5]}

from bisect import bisect_right
from collections import defaultdict


class SubsequenceChecker:
    """Preprocess t once, then answer many is_subsequence queries quickly."""

    def __init__(self, t: str) -> None:
        self._positions: defaultdict[str, list[int]] = defaultdict(list)
        for index, char in enumerate(t):
            self._positions[char].append(index)

    def check(self, s: str) -> bool:
        prev = -1
        for char in s:
            spots = self._positions.get(char)
            if not spots:
                return False
            # First position strictly greater than prev.
            k = bisect_right(spots, prev)
            if k == len(spots):
                return False
            prev = spots[k]
        return True

Complexity Analysis

• Time — one pass over t, with n = |s| and m = |t|. Effectively O(m), since the pointer into s never outpaces it.
• Space — two indices.

The preprocessing variant is O(m) setup and O(m) space, then O(n log m) per query — the right trade when queries are numerous.

Edge Cases

Related Problems

• Find the Index of the First Occurrence in a String — the substring version, which requires adjacency
• Merge Sorted Array — two pointers advancing at independent rates
• Binary Search — the tool behind the follow-up optimisation