392. Is Subsequence - Explanation

Description

You are 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. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "node", t = "neetcode"

Output: true

Example 2:

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

Output: false

Constraints:

0 <= s.length <= 100
0 <= t.length <= 10,000
s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 1,000,000,000, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

To check if s is a subsequence of t, we need to find all characters of s in t in the same order, though not necessarily contiguous. Recursively, we compare the current characters of both strings: if they match, we advance both pointers; if they do not match, we only advance the pointer in t to continue searching. The base cases are reaching the end of s (success) or the end of t before finishing s (failure).

Algorithm

Define a recursive function rec(i, j) where i is the index in s and j is the index in t.
Base cases:
- If i == len(s), all characters matched, return true.
- If j == len(t), ran out of characters in t, return false.
If s[i] == t[j], both characters match, so recurse with rec(i + 1, j + 1).
Otherwise, skip the current character in t and recurse with rec(i, j + 1).
Start with rec(0, 0).

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        def rec(i, j):
            if i == len(s):
                return True
            if j == len(t):
                return False

            if s[i] == t[j]:
                return rec(i + 1, j + 1)
            return rec(i, j + 1)
        return rec(0, 0)

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ and $m$ is the length of the string $t$ .

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution may recompute the same subproblems multiple times. By adding memoization, we cache the result for each (i, j) state so that each pair is computed at most once. This transforms the exponential worst case into a polynomial time solution while keeping the recursive structure intact.

Algorithm

Create a 2D memo table initialized to -1.
Define a recursive function rec(i, j):
- Base cases same as before.
- If memo[i][j] is already computed, return the cached result.
- Compute the result based on whether characters match or not.
- Store the result in memo[i][j] and return it.
Call rec(0, 0).

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        memo = [[-1] * m for _ in range(n)]

        def rec(i, j):
            if i == n:
                return True
            if j == m:
                return False
            if memo[i][j] != -1:
                return memo[i][j] == 1
            if s[i] == t[j]:
                memo[i][j] = 1 if rec(i + 1, j + 1) else 0
            else:
                memo[i][j] = 1 if rec(i, j + 1) else 0
            return memo[i][j] == 1

        return rec(0, 0)

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the length of the string $s$ and $m$ is the length of the string $t$ .

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion with memoization, we can fill a DP table iteratively from the end of both strings toward the beginning. The value dp[i][j] represents whether s[i:] is a subsequence of t[j:]. If the characters match, we look at dp[i+1][j+1]. Otherwise, we look at dp[i][j+1] (skip the character in t). The base case is that any suffix of s starting at len(s) is trivially a subsequence of anything (empty string).

Algorithm

Create a 2D DP table of size (n+1) x (m+1) initialized to false.
Set dp[n][j] = true for all j (empty remainder of s is always a subsequence).
Iterate i from n-1 down to 0, and j from m-1 down to 0:
- If s[i] == t[j], set dp[i][j] = dp[i+1][j+1].
- Otherwise, set dp[i][j] = dp[i][j+1].
Return dp[0][0].

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        dp = [[False] * (m + 1) for _ in range(n + 1)]

        for j in range(m + 1):
            dp[n][j] = True

        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                if s[i] == t[j]:
                    dp[i][j] = dp[i + 1][j + 1]
                else:
                    dp[i][j] = dp[i][j + 1]

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the length of the string $s$ and $m$ is the length of the string $t$ .

4. Two Pointers

Intuition

The most efficient approach uses two pointers since we only need to make a single pass through both strings. Pointer i tracks our position in s, and pointer j tracks our position in t. We always advance j, but only advance i when we find a matching character. If we reach the end of s, all characters were found in order. This is optimal because each character in t is examined exactly once.

Algorithm

Initialize pointers i = 0 and j = 0.
While i < len(s) and j < len(t):
- If s[i] == t[j], increment i.
- Always increment j.
Return i == len(s).

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)

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(1)$

Where $n$ is the length of the string $s$ and $m$ is the length of the string $t$ .

5. Follow-Up Solution (Index Jumping)

Intuition

When checking many strings against the same t, the two-pointer approach becomes inefficient because we scan t repeatedly. Instead, we precompute for each position in t the next occurrence of each character. This lets us jump directly to the next matching character rather than scanning. The preprocessing takes O(26 * m) time and space, but each subsequence query then takes only O(n) time regardless of the length of t.

Algorithm

Build a 2D array store of size m x 26. Entry store[j][c] holds the smallest index >= j where character c appears in t.
Fill store from right to left:
- Initialize store[m-1] with m + 1 for all characters except t[m-1].
- For each position j from m-2 to 0, copy store[j+1] and update the entry for t[j].
To check if s is a subsequence:
- Start at j = 0.
- For each character in s, look up its next position from store[j] and jump to it.
- If the jump goes beyond m, return false.
Return true if all characters are matched.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        if m == 0:
            return n == 0

        store = [[m + 1] * 26 for _ in range(m)]
        store[m - 1][ord(t[m - 1]) - ord('a')] = m - 1

        for i in range(m - 2, -1, -1):
            store[i] = store[i + 1][:]
            store[i][ord(t[i]) - ord('a')] = i

        i, j = 0, 0
        while i < n and j < m:
            j = store[j][ord(s[i]) - ord('a')] + 1
            if j > m:
                return False
            i += 1

        return i == n

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the length of the string $t$ .