Introduction

A string s is a subsequence of another string t if you can delete some characters from t without changing the order of the characters that remain and obtain s. The standard solution is a two-pointer scan that runs in linear time and is usually the best choice unless you need to answer many subsequence queries against the same large target string.

Use Two Pointers for the Normal Case

The simplest algorithm keeps one pointer in s and one in t:

• advance through t
• whenever characters match, advance in s
• if you reach the end of s, it is a subsequence

Python example:

1def is_subsequence(s: str, t: str) -> bool:
2    i = 0
3
4    for ch in t:
5        if i < len(s) and s[i] == ch:
6            i += 1
7
8    return i == len(s)
9
10
11print(is_subsequence("abc", "ahbgdc"))
12print(is_subsequence("axc", "ahbgdc"))

This works in O(len(t)) time and O(1) extra space, which is optimal for a single query when you must inspect the target string in order.

The logic is straightforward: characters in s must appear in t in the same order, but they do not need to be adjacent.

Walk Through an Example

Take:

• 's = "abc"'
• 't = "ahbgdc"'

The algorithm compares:

• ''a' with characters in t until it finds 'a''
• then 'b' until it finds 'b'
• then 'c' until it finds 'c'

Since all three characters are found in order, "abc" is a subsequence of "ahbgdc".

For "axc" against the same t, the scan never finds 'x', so the result is false.

This is why the two-pointer solution is both easy to reason about and efficient.

Handle Edge Cases Explicitly

A few special cases are worth keeping in mind:

• the empty string is a subsequence of every string
• a non-empty string is never a subsequence of an empty string
• if s is longer than t, the answer is automatically false

You can incorporate some of those checks early:

1def is_subsequence(s: str, t: str) -> bool:
2    if not s:
3        return True
4    if len(s) > len(t):
5        return False
6
7    i = 0
8    for ch in t:
9        if s[i] == ch:
10            i += 1
11            if i == len(s):
12                return True
13    return False

This version can stop early as soon as the last required character is matched.

Optimize Only If You Have Many Queries

If you need to check thousands or millions of candidate strings against the same target string t, the simple scan may become too slow overall. In that situation, preprocess t so you can jump to the next occurrence of each character quickly.

One approach is to build an index of character positions:

1from bisect import bisect_right
2from collections import defaultdict
3
4
5def build_index(t: str):
6    pos = defaultdict(list)
7    for i, ch in enumerate(t):
8        pos[ch].append(i)
9    return pos
10
11
12def is_subsequence_many(s: str, index) -> bool:
13    current = -1
14    for ch in s:
15        positions = index.get(ch)
16        if not positions:
17            return False
18        j = bisect_right(positions, current)
19        if j == len(positions):
20            return False
21        current = positions[j]
22    return True

This is more complex, so it is worth it only when the same t is reused for many subsequence tests.

For one-off checks, the two-pointer method is still better.

Common Pitfalls

The biggest mistake is confusing subsequence with substring. A subsequence allows gaps; a substring requires contiguity.

Another issue is overcomplicating the solution for a single query. The two-pointer scan is already optimal enough for normal use.

Developers also sometimes forget the empty-string case. By definition, the empty string is always a subsequence.

Finally, if you optimize for many queries with a precomputed index, make sure you only pay that preprocessing cost when the same target string is reused often enough to justify it.

Summary

• The standard way to test subsequence status is a two-pointer scan.
• It runs in linear time in the length of the target string and uses constant extra space.
• A subsequence preserves order but does not require adjacent characters.
• The empty string is always a subsequence.
• More advanced indexing approaches only make sense when you must test many strings against the same target.