Skip to content
Optimal Lab

Two Pointers · 173Easy

Is Subsequence

Given two strings s and t, return true if s is a subsequence of t: it can be formed by deleting some (possibly zero) characters of t without changing the order of the rest.

Constraints

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • s and t consist only of lowercase English letters.

Examples

isSubsequence("abc", "ahbgdc")  ->  true
isSubsequence("axc", "ahbgdc")  ->  false
isSubsequence("", "abc")        ->  true   // the empty string is a subsequence of anything
isSubsequence("", "")           ->  true   // both empty
isSubsequence("ba", "abc")      ->  false   // order matters
isSubsequence("abc", "ab")      ->  false   // s longer than t can never match

Edge cases

  • s longer than t can never match.
  • Order matters: "ba" is not a subsequence of "abc".
  • FOLLOW-UP
  • If there are many incoming s strings (say 10^9) against the same t, how would you change
  • your approach?
Show the target complexity (spoiler)
Naive
Exponential — generate subsequences of t and compare.
Target
O(|t|) time, O(1) space — one pointer in each string; advance the s pointer only on a match. (Follow-up: per-letter index lists of t plus binary search.)

Solve it

By hand, in your editor. The runner checks answers and timing.

git clone https://github.com/sarmadkung/optimal-round
cd optimal-round
# open problems/02-two-pointers/173-is-subsequence.js
./practice c 173
Open the file on GitHub ↗

Stuck? Watch the pattern run

Interactive sessionTwo pointers: most water →