Watch 10 video solutions for Is Subsequence, a easy level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by NeetCode has 59,162 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
Input: s = "abc", t = "ahbgdc" Output: true
Example 2:
Input: s = "axc", t = "ahbgdc" Output: false
Constraints:
0 <= s.length <= 1000 <= t.length <= 104s and t consist only of lowercase English letters.Follow up: Suppose there are lots of incoming
s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?Problem Overview: Given two strings s and t, determine whether s is a subsequence of t. A subsequence keeps the relative order of characters but does not require them to be contiguous. The task is to scan t and verify that every character in s appears in order.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This is the standard solution using the two pointers pattern. Maintain one pointer for s and another for t. Iterate through t; whenever t[j] matches s[i], advance the pointer for s. Continue scanning until either all characters in s are matched or t is exhausted. The key insight: subsequence checking only requires preserving order, so a single pass through t is enough. This approach runs in O(|t|) time and O(1) space because it only uses two indices. It works well when you check a single pair of strings and is the most common interview solution for problems involving string traversal.
Approach 2: Preprocessing with Character Index Lists (O(n + m log n) time, O(n) space)
The follow-up version asks what happens if you must check billions of candidate strings s against the same t. Instead of scanning t every time, preprocess it by storing the indices of each character in a map. For example, build a dictionary where each character points to a sorted list of positions where it appears in t. For each character in s, use binary search to find the smallest index greater than the previously matched position. This converts repeated scanning into fast lookups. Preprocessing takes O(|t|) time and space. Each query string s then runs in O(|s| log |t|) due to binary search. This pattern appears in advanced dynamic programming and query optimization problems where the same dataset is reused.
Recommended for interviews: The two-pointer solution is what interviewers expect first. It shows you understand subsequence properties and can implement an efficient single-pass scan with O(n) time and constant space. Mentioning the preprocessing approach during follow-ups demonstrates deeper problem-solving skills and awareness of scaling when many queries share the same base string.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(|t|) | O(1) | Best for single queries where you only need to check one pair of strings. |
| Preprocessing with Index Lists + Binary Search | O(|t|) preprocessing + O(|s| log |t|) per query | O(|t|) | Useful when many different strings must be checked against the same base string t. |