AlgoMaster Logo

Is Subsequence

Last Updated: March 20, 2026

easy
5 min read

Understanding the Problem

We need to check whether every character of s appears in t, in the same order, but not necessarily consecutively. We can skip characters in t, but we can't rearrange them.

Think of it like scanning through a book (t) looking for specific letters in a specific order (s). You read the book from left to right, and every time you spot the next letter you need, you mark it off your list. If you reach the end of your list before the book runs out, you've found your subsequence. If the book ends first, you haven't.

The follow-up is where this problem gets interesting. Checking one string against t is straightforward. But what if you need to check a billion strings against the same t? A linear scan for each one adds up fast. That's where preprocessing t pays off.

Key Constraints:

  • 0 <= s.length <= 100 → s is very short. Even an O(n^2) approach on s alone would be trivial.
  • 0 <= t.length <= 10^4 → t can be moderately long. O(m) per query is fine for a single check, but if there are billions of queries, we want to minimize work per query.
  • lowercase English letters only → Just 26 possible characters. This is a strong hint for the follow-up: we can build a lookup structure indexed by character.
  • s can be empty → An empty string is a subsequence of everything. Don't forget this edge case.

Approach 1: Two Pointers

Intuition

The most natural approach: walk through both strings simultaneously. Use one pointer for s and one for t. Every time the characters match, advance the pointer on s. Always advance the pointer on t. If we match all characters of s before running out of t, then s is a subsequence.

Why does this greedy strategy work?

When we find a matching character in t, there's no benefit to skipping it and hoping for a "better" match later. The characters in s must appear in order, and taking the earliest available match in t leaves the most room for matching subsequent characters. This is a classic greedy argument: the earliest match is always at least as good as any later match.

Algorithm

  1. Initialize two pointers: i = 0 for s, j = 0 for t.
  2. While both pointers are within bounds:
    • If s[i] == t[j], we've matched a character. Advance both i and j.
    • Otherwise, advance only j (skip this character in t).
  3. After the loop, if i == s.length, all characters of s were matched. Return true. Otherwise, return false.

Example Walkthrough

1Initialize: s="abc", i=0, j=0. Looking for 'a'
0
i→'a'
a
j
1
h
2
b
3
g
4
d
5
c
1/6

Code

For a single query, this is already optimal. But the follow-up asks what happens when we have billions of queries against the same t. Every query re-scans t from scratch. Can we preprocess t once so each query skips the linear scan?

Approach 2: Binary Search with Preprocessing

Intuition

The follow-up asks: what if we check many strings against the same t? The two-pointer approach scans t from scratch for every query. If t never changes, we should preprocess it once and reuse that information.

Here's the idea: for each character in the alphabet, store the sorted list of indices where that character appears in t. Then, for each character in s, instead of scanning t linearly, we binary search for the next valid position.

For example, if t = "ahbgdc", we'd build this index map:

  • 'a' → [0]
  • 'b' → [2]
  • 'c' → [5]
  • 'd' → [4]
  • 'g' → [3]
  • 'h' → [1]

To check if s = "abc" is a subsequence, we start at position -1 (before the string). For 'a', binary search for the smallest index > -1 in [0]. That gives us 0. For 'b', search for the smallest index > 0 in [2]. That gives us 2. For 'c', search for the smallest index > 2 in [5]. That gives us 5. We found valid positions for all characters, so it's a subsequence.

Algorithm

  1. Preprocess: Build a hash map where each key is a character, and the value is a sorted list of indices where that character appears in t.
  2. For each query string s:
    • Initialize prevIndex = -1 (the position of the last matched character).
    • For each character c in s:
      • Look up the index list for c. If the list doesn't exist, return false.
      • Binary search for the smallest index in the list that is greater than prevIndex.
      • If no such index exists, return false.
      • Otherwise, update prevIndex to this index.
    • If all characters are matched, return true.

Example Walkthrough

1Preprocessed index map: a→[0], h→[1], b→[2], g→[3], d→[4], c→[5]. prevIndex=-1
0
a
1
h
2
b
3
g
4
d
5
c
1/5

Code

Each query still takes O(n log m) because of the binary search. What if we precomputed the answer for every (position, character) pair, so each lookup became O(1)?

Approach 3: Dynamic Programming (Next Occurrence Matrix)

Intuition

We can precompute a "jump table" for t: for every position j and every character c, store the index of the next occurrence of c at or after position j. This turns each character lookup into an O(1) table access.

The table is built by scanning t from right to left. At position j, the next occurrence of t[j] is j itself. For all other characters, the next occurrence is the same as what it was at position j + 1. This right-to-left scan fills the entire table in O(26 * m) time.

Once the table is built, checking a query is simple: start at position 0 in t, look up the next occurrence of s[0], jump there, then look up the next occurrence of s[1] from the new position, and so on. Each lookup is O(1), so the total per query is O(n).

Algorithm

  1. Preprocess: Build a 2D array next of size (m + 1) x 26.
    • Initialize the last row (position m) with -1 for all characters (no characters after the end).
    • Scan from j = m - 1 down to 0:
      • Copy row j + 1 into row j.
      • Set next[j][t[j] - 'a'] = j (this character is available at position j).
  2. For each query string s:
    • Start at position j = 0.
    • For each character c in s:
      • Look up next[j][c - 'a'].
      • If it's -1, return false (character not available).
      • Otherwise, set j = next[j][c - 'a'] + 1 (move past this matched character).
    • If all characters are matched, return true.

Example Walkthrough

1Build next occurrence matrix for t="ahbgdc" (right to left scan)
0
a
1
h
2
b
3
g
4
d
5
c
1/6

Code