#392

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Is Subsequence

Determine if one string is a subsequence of another using state transition dynamic programming for accurate character matching.

two pointers string dynamic programming

Problem Statement

Given two strings s and t, implement a function that returns true if s can be formed by deleting some characters from t without changing the relative order of remaining characters. A subsequence requires all characters in s to appear in order within t, but they do not need to be contiguous.

For example, with s = "abc" and t = "ahbgdc", the output should be true because 'a', 'b', and 'c' appear in order. However, for s = "axc" and t = "ahbgdc", the output is false because 'x' does not appear in t in the correct order. Constraints: 0 <= s.length <= 100, 0 <= t.length <= 10^4, all characters are lowercase English letters.

Examples

Example 1

Input: s = "abc", t = "ahbgdc"

Output: true

Example details omitted.

Example 2

Input: s = "axc", t = "ahbgdc"

Output: false

Example details omitted.

Constraints

0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.

Solution Approach

Two Pointers Scan

Initialize two pointers, one for s and one for t. Iterate through t, advancing the s pointer whenever characters match. If the s pointer reaches the end of s, return true; otherwise, return false.

Dynamic Programming Table

Precompute next occurrence positions for each character in t. Build a DP table mapping each index in t to the next index where each character appears. Iterate through s using the table to jump to valid positions quickly, returning false if a character cannot be matched.

Binary Search Optimization

After preprocessing t into lists of indices per character, use binary search to find the next valid position for each character in s. This reduces repeated scanning and is efficient when multiple s queries target the same t string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies: simple two pointers is O(n) with n = t.length; DP preprocessing is O(n 26) and query per s is O(m) with m = s.length; binary search approach preprocesses t in O(n) and answers each s in O(m log k), where k is average occurrences per character. Space complexity ranges from O(1) for two pointers to O(n 26) for DP tables.

What Interviewers Usually Probe

Focus on maintaining character order while scanning t; interviewer may hint at pointer misalignment.
Expect discussion of repeated queries, signaling a DP or preprocessed optimization.
Be ready to explain why naive nested loops fail with longer t, showing awareness of time complexity.

Common Pitfalls or Variants

Common pitfalls

Incorrectly incrementing pointers can skip valid matches, producing false negatives.
Confusing contiguous substring with subsequence leads to wrong logic.
Not handling empty s or t properly may cause boundary errors or incorrect returns.

Follow-up variants

Check if s is a subsequence of multiple t strings efficiently using DP preprocessing.
Return the length of the longest subsequence of s present in t.
Allow wildcard characters in s that can match any single character in t.

FAQ

What is the easiest way to check if s is a subsequence of t?

Use a two pointers approach: iterate through t, moving the s pointer when characters match, returning true if s is fully traversed.

How does dynamic programming improve the Is Subsequence problem?

DP allows precomputing next character positions in t, reducing repeated scans and enabling fast queries when checking multiple s strings against the same t.

Can I use recursion for this problem?

Yes, but simple recursion without memoization may exceed time limits on longer t strings; iterative two pointers or DP is safer.

What should I watch out for with empty strings?

An empty s is always a subsequence of any t, but an empty t cannot contain any non-empty s; handle these as special cases.

Is this problem pattern always solved with two pointers?

Two pointers is the canonical approach for single queries, but DP or binary search optimizations are preferred when multiple queries target the same t.

terminal

Solution

Solution 1: Two Pointers

We define two pointers $i$ and $j$ to point to the initial position of the string $s$ and $t$ respectively. Each time we compare the two characters pointed to by the two pointers, if they are the same, both pointers move right at the same time; if they are not the same, only $j$ moves right. When the pointer $i$ moves to the end of the string $s$, it means that $s$ is the subsequence of $t$.

1

2

3

4

5

6

7

8

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

Continue Practicing

#647 palindromic substrings #5 longest palindromic substring #838 push dominoes