Skip to main content

392. Is Subsequence

easy

Check whether one string appears as a subsequence of another. Two-pointer solves it in linear time; DP framing prepares you for the follow-up where the source is queried billions of times.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

Input
s = "abc", t = "ahbgdc"
Output
true

Explanation: The characters a, b, c appear in t in order.

Example 2

Input
s = "axc", t = "ahbgdc"
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two pointers: advance through t; advance through s only on a match.

Hint 2

DP framing: dp[i][j] = true if s[0..i-1] is a subsequence of t[0..j-1]. Useful when t is fixed and many queries come in.

Hint 3

If you reach the end of s, you matched everything; return true.

Solution approach

Reveal approach

Two-pointer scan is the linear-time solution. Initialize i = 0 (pointer into s) and j = 0 (pointer into t). While both pointers are in range, if s[i] == t[j] increment i; always increment j. Return i == s.length. The DP framing for the follow-up: define subproblem dp[i][j] = whether s[0..i-1] is a subsequence of t[0..j-1]. The transition is dp[i][j] = dp[i-1][j-1] if s[i-1] == t[j-1] else dp[i][j] = dp[i][j-1]. Base case dp[0][j] = true (empty string is a subsequence of anything). For the indexed-by-character preprocessing variant, build next[t.length][26] where next[i][c] is the next index >= i in t containing character c — each query then runs in O(s.length). Time O(s.length + t.length), space O(1).

Complexity

Time
O(s.length + t.length)
Space
O(1)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Is Subsequence and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →