Is Subsequence: definition
A subsequence keeps characters in their original order but may skip characters between them. This problem applies the two-pointer technique to two strings.
Task example: Is Subsequence
Given lowercase strings s and t, return True if every character of s can be matched in t in order. Otherwise return False. Characters need not be adjacent. Do not sort or reorder either string.
An empty s is a subsequence of every string. Each repeated letter needs its own matching position in t.
Search and slice: video explanation
s = "abc", t = "ahbgdc" → True
Prefer reading? Follow the steps below.
- For each char in s, find its first occurrence in the remaining t. If find returns -1, return False immediately.
- After a match, replace t with t[pos + 1:]. Continue only after that match, so positions cannot be reused or reordered.
- For abc in ahbgdc: matching a leaves hbgdc, matching b leaves gdc, and matching c leaves an empty suffix. All characters matched: True.
Time complexity · O(mn)
m = len(s), n = len(t). For non-empty inputs, repeated slices may copy up to n characters for each of m matches. When m = n and every letter matches, copying is quadratic. Empty s takes O(1).
Space complexity · O(n)
Space complexity is O(n) for temporary suffix strings. Python slices copy characters; rebinding t does not modify the caller’s original string.
Two pointers: video explanation
s = "abc", t = "ahbgdc" → True
Prefer reading? Follow the steps below.
- Start i = j = 0. i points to the next required character in s; j scans t. Continue while both pointers are inside their strings.
- If s[i] equals t[j], advance i. Always advance j. A mismatch skips a character in t, never a required character in s.
- Return i == len(s). For abc, all three letters match. For axc, t ends while i still points to x, so the answer is False.
Why it works: choosing the earliest available match leaves at least as much text for the remaining letters as choosing a later match. We never need to move backwards.
Time complexity · O(n)
j visits each position of t at most once, so worst-case time is O(n). The loop stops early when all of s has matched.
Space complexity · O(1)
Only i and j are stored: O(1) extra space. Unlike search and slice, there are no suffix copies. Both input strings remain unchanged.