Is Subsequence: Two-Pointer Matching

Given two strings s and t, return True if s is a subsequence of t, and False otherwise. A subsequence is a sequence of characters that appears in the same order within another string, but not necessarily consecutively. You can skip characters in t, but you cannot rearrange the characters of s.

This is LeetCode 392: Is Subsequence, and it is one of the cleanest two-pointer problems you will encounter. No sorting, no edge-case gymnastics, just two pointers walking through two strings.

A few examples:

• s = "ace", t = "abcde" returns True. You can find a, c, e in order inside t by skipping b and d.
• s = "aec", t = "abcde" returns False. After matching a and e, there is no c left after e in t.
• s = "", t = "anything" returns True. An empty string is a subsequence of every string.

The two-pointer approach

The idea is to use two pointers: i walks through s and j walks through t. At each step, compare s[i] with t[j]. If they match, advance both pointers, because you have matched one more character of s. If they do not match, advance only j, because you are skipping a character in t that does not contribute to the subsequence.

When you are done, check whether i has reached the end of s. If it has, every character in s was matched in order. If j reaches the end of t first while i still has characters left, then s is not a subsequence.

def is_subsequence(s, t):
    i, j = 0, 0

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

    return i == len(s)

That is the entire solution. No helper functions, no preprocessing, no extra data structures. The key decision at each step is simple: does the current character in t match the current character we need from s? If yes, move on to the next character in s. Either way, move on to the next character in t.

Visual walkthrough

Let's trace the algorithm on s = "ace" and t = "abcde". The orange pointer i tracks our position in s, and the green pointer j tracks our position in t.

Notice the rhythm: j always advances, but i only advances on a match. This means j does all the scanning work, and i just waits for the right characters to appear. By the time j finishes scanning t, either i has matched everything (subsequence found) or it has not (not a subsequence).

Why this works

The greedy argument is simple. When you see a character in t that matches the current character you need from s, there is never a reason to skip it. Matching it now does not prevent you from matching any future character, because the remaining characters of s all come after this one in order. Matching greedily, at the earliest possible position, leaves the maximum remaining portion of t available for the rest of s.

This is what makes the problem easy: there are no tradeoffs to consider. You never need to choose between matching now or saving a character for later. The greedy choice is always optimal.

Complexity analysis

Where n is the length of t and m is the length of s. The two-pointer solution is optimal for a single query. Each character of t is visited at most once, and each character of s is visited at most once, so the total work is O(n + m) which simplifies to O(n) since m is at most n.

Space: O(1). Two integer pointers. Nothing else.

The building blocks

Is Subsequence is built from one fundamental technique: same-direction scanning with two pointers. Both pointers move left to right through their respective strings, but at different speeds. The pointer on t moves every step, while the pointer on s only moves on a match.

This is different from the converging two-pointer pattern used in problems like Valid Palindrome or Container With Most Water, where the pointers start at opposite ends and move inward. Here, both pointers start at the beginning and move in the same direction.

The same-direction scanning pattern shows up in several other problems:

• Merge Two Sorted Lists: two pointers walk through two sorted sequences, picking the smaller element at each step
• Remove Duplicates from Sorted Array: a slow pointer marks the write position while a fast pointer scans ahead
• Move Zeroes: same slow/fast pointer structure, partitioning in-place

What all these problems share is the asymmetry: one pointer drives the scan, and the other pointer reacts to conditions. In Is Subsequence, j drives and i reacts. Once you recognize this pattern, the code writes itself.

Edge cases

Empty s. An empty string is a subsequence of every string. The while loop never executes because i starts at 0 which equals len(s), and we return True immediately.

Empty t. If s is non-empty and t is empty, the while loop never executes and i is still 0, which is less than len(s). We return False.

s longer than t. If s has more characters than t, it cannot be a subsequence. The algorithm handles this naturally: j reaches the end of t before i reaches the end of s.

Identical strings. Every character matches, both pointers advance together, and i reaches the end at the same time as j. Return True.

s is a single character. The loop scans t until it finds the character or reaches the end. This is essentially a linear search.

From understanding to recall

Is Subsequence is one of the easiest LeetCode problems. Most people can read the solution and understand it in under a minute. But the value is not in the problem itself. It is in the two-pointer pattern it teaches.

The same-direction scan with one fast pointer and one conditional pointer is a building block that appears in dozens of problems. When you drill this pattern until it is automatic, problems like Merge Sorted Array, Move Zeroes, and even more complex sliding window setups become faster to solve because you are not reinventing the pointer logic each time.

Reading about it once is not enough. Try writing the solution from scratch tomorrow without looking at this page. If you can do it, the pattern is in your long-term memory. If you stumble on the loop condition or the return value, that is exactly the kind of detail that spaced repetition is designed to catch.

Related posts

• Valid Palindrome - Two pointers converging from opposite ends, a complementary pattern to the same-direction scan used here
• Longest Common Subsequence - A harder subsequence problem that uses 2D dynamic programming instead of two pointers
• Two Sum - The classic intro to using pointers and lookups to avoid brute force comparisons