Is Subsequence
Easy · Two Pointers · Two Pointers · String · Dynamic Programming
Problem
Given two strings s and t, return true if s is a subsequence of t, and false otherwise.
s is a subsequence of t when you can delete some characters of t (possibly none), without changing the order of the rest, and be left with exactly s. The empty string is a subsequence of every string.
Examples
Input: s = "ace", t = "abcde" Output: true
Keep a, c and e from t and delete b and d.
Input: s = "aec", t = "abcde" Output: false
The only c in t comes before the only e, so a, e, c cannot be kept in that order.
Input: s = "", t = "xyz" Output: true
Deleting every character of t leaves the empty string.
Constraints
- 0 <= len(s) <= 100
- 0 <= len(t) <= 10^4
- s and t contain only lowercase English letters
Approaches
- Next-occurrence table (many queries) — time O(26 · |t| + |s|), space O(26 · |t|)
Follow-up
If you had to check a huge number of different s strings against the same t, scanning t for each one costs O(|t|) per query. Build once, for every position of t and every letter, the next index where that letter appears (or a list of positions per letter and binary search). Each query then costs O(|s|) or O(|s| log |t|) and never rereads t.
Related problems
Start free on Cariara · Coding problems · System design studio
