Algorithm

Is Subsequence

Two Pointer Pattern

Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative order of the remaining characters. (i.e., 'ace' is a subsequence of 'abcde' while 'aec' is not). Follow-up: Suppose there are lots of incoming s strings, say s1, s2, ..., sk where k >= 10^9, and you want to check each one against a given t. What would you do?

CONSTRAINTS
  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • s and t consist only of lowercase English letters
  • Follow-up: What if there are many incoming s strings against a fixed t?
EXAMPLE 1
Input: s = "abc", t = "ahbgdc"
Output: true
"a" matches at index 0, "b" matches at index 2, "c" matches at index 5. All characters of s appear in order in t.
EXAMPLE 2
Input: s = "axc", t = "ahbgdc"
Output: false
"a" matches at 0, but "x" does not appear in t after position 0. The scan exhausts t without matching all of s.
EXAMPLE 3
Input: s = "", t = "ahbgdc"
Output: true
An empty string is a subsequence of any string — there are no characters in s to match, so the condition is satisfied trivially.
What is the difference between a subsequence and a substring?
A substring must be contiguous (consecutive characters). A subsequence preserves relative order but allows gaps. 'ace' is a subsequence but not a substring of 'abcde'.
What if s is longer than t?
It is impossible for s to be a subsequence of a shorter string t. The logic handles this naturally — j exhausts t before i exhausts s, and we return false.

We want to verify if a short string is completely contained within a longer string in the correct relative order. We are allowed to skip as many characters in the longer string as we like, but we cannot rearrange the letters we keep. For example, if we want to find "ace" inside "abcde", we can keep the 'a', 'c', and 'e' and delete the 'b' and 'd'. However, we cannot find "aec" because the letters appear in the wrong order. How can we verify this ordering relationship efficiently?

The Combinatorial Explosion

The most direct way is to construct every single possible subsequence of the longer string, one by one. Once we have a giant library of every possible character combination in its original relative order, we search through that library to see if our short string is in there.

While this sounds simple, it is a combinatorial nightmare. A string of length M generates 2^M possible subsequences. If the longer string has only 50 characters, we would have to generate and check over one quadrillion combinations, making this approach completely unusable.

python
# Generate every possible combination in relative order
all_subsequences = generate_all_subsequences(large_word)

# Check if the target is one of them
for sub in all_subsequences:
    if sub == small_word:
        return True

return False
The Needle & The Haystack

To solve this in linear time, we can scan both strings in a single pass from left to right. We set up two pointers, each with a strict and clear contract:
- The Target Pointer (s_idx): Points to the specific character we are currently looking for in the short string s.
- The Search Pointer (t_idx): Points to our current search position in the longer string t.

By moving these pointers dynamically, we can inspect characters in-place without ever generating external combinations.

Greedy Match Forwarding

Our search pointer (t_idx) steadily marches through the longer string t, one letter at a time. At each step, we look at what t_idx is pointing to. If it matches the letter that s_idx is searching for, we have found a match! We immediately move the target pointer (s_idx) forward by one step to search for the next letter. The search pointer (t_idx) always advances on every iteration, regardless of whether a match was found.

This greedy choice is mathematically guaranteed to work: matching the earliest possible occurrence of a character leaves the largest possible remaining space in string t to match the rest of string s. If the target pointer (s_idx) successfully reaches the end of string s, we have confirmed the entire subsequence exists in order.

python
s_idx = 0
t_idx = 0

# Scan through the longer string
while t_idx < len(t) and s_idx < len(s):
    # If we find the letter we need, advance our target search
    if s[s_idx] == t[t_idx]:
        s_idx += 1
    # Always advance the search index in the source string
    t_idx += 1

# If we matched every character in order, s_idx will reach the end
return s_idx == len(s)
Worked Example:Tracking the Sequence
0
a
t_idx
1
h
2
b
3
g
4
d
5
c
We start at the beginning. s[0] ('a') matches t[0] ('a'). We advance our target search to 'b'.
0
a
1
h
t_idx
2
b
3
g
4
d
5
c
We scan 'h' at t[1]. It does not match our current target 'b', so we proceed.
0
a
1
h
2
b
t_idx
3
g
4
d
5
c
We scan 'b' at t[2]. It matches our target 'b'. We advance our target search to 'c'.
0
a
1
h
2
b
3
g
4
d
5
c
t_idx
After scanning past 'g' and 'd', we match 'c' at t[5]. We have successfully matched all characters of s in order.
Interactive Strategy Visualization

Greedy Subsequence Check

Same-Direction Two Pointers

s (subsequence)
i=0
a
b
c
↕ MATCH?
t (target)
j=0
a
0
h
1
b
2
g
3
d
4
c
5
MATCHED
0/3
SCANNED
1/6
STATUS
⏳ Scanning...
Compare s[0]='a' with t[0]='a'. Match!

Key Insight

Pointer i only advances on a match, while j always advances. This greedy strategy works because matching a character earlier in t never hurts — it leaves more room for future matches.

Asymmetric Pointers

Unlike converging pointers that move toward each other, these two pointers move in the same direction at different speeds. One is a "scanner" (always advancing), the other is a "matcher" (only on match).

O(2ᴹ) Generate Subsequences
→
O(N + M) Time · O(1) Space Two-Pointer Scan