LeetCode 392: Is Subsequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 392: Is Subsequence?

LeetCode 392: Is Subsequence provides two strings, s and t, and your task is to check if s is a subsequence of t—meaning all characters of s appear in t in the same order, though not necessarily consecutive. It’s a problem that tests your ability to match sequences efficiently!

Problem Statement

• Input:
• s: Potential subsequence string.
• t: Main string to check against.
• Output: Boolean - True if s is a subsequence of t, False otherwise.
• Rules:
• Characters in s must appear in t in the same relative order.
• Characters need not be contiguous in t.

Constraints

• 0 <= s.length <= 100
• 0 <= t.length <= 10⁴
• Both strings contain only lowercase English letters.

Examples

• Input: s = "abc", t = "ahbgdc"
• Output: True
• 'a', 'b', 'c' appear in order in "ahbgdc".
• Input: s = "axc", t = "ahbgdc"
• Output: False
• No 'x' in "ahbgdc".
• Input: s = "", t = "ahbgdc"
• Output: True
• Empty string is a subsequence of any string.

These show the subsequence hunt—let’s solve it!

Understanding the Problem: Checking Subsequence

To tackle LeetCode 392 in Python, we need to: 1. Verify if all characters in s appear in t in the same order. 2. Allow non-consecutive matches in t. 3. Handle efficiently given t’s potential length.

A naive approach might check each character’s position recursively, but that’s slow. We’ll use:

• Best Solution: Two pointers—O(n) time, O(1) space—fast and optimal.
• Alternative Solution: Dynamic programming—O(m * n) time, O(m * n) space—thorough but overkill.

Let’s match with the best solution!

Best Solution: Two Pointers

Why This Is the Best Solution

The two-pointer approach runs in O(n) time (n is length of t) with O(1) space by using one pointer for s and one for t, advancing them as matches are found. It’s the most efficient—linear time, no extra space, and perfectly suited for a subsequence check!

How It Works

Think of it like a treasure hunt:

• Pointers:
• i for s (subsequence index).
• j for t (main string index).
• Process:
• Iterate j through t.
• If t[j] matches s[i], increment i.
• If i reaches len(s), all chars found in order.
• Result: True if all of s matched, False otherwise.

It’s like following a trail of clues in order!

Step-by-Step Example

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

• Init: i = 0 (s), j = 0 (t).
• j=0: 'a' = 'a', i = 1.
• j=1: 'h' ≠ 'b', j = 2.
• j=2: 'b' = 'b', i = 2.
• j=3: 'g' ≠ 'c', j = 4.
• j=4: 'd' ≠ 'c', j = 5.
• j=5: 'c' = 'c', i = 3.
• End: i = 3 = len(s), return True.

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

• j=0: 'a' = 'a', i = 1.
• j=1-5: No 'x', i stuck at 1, return False.

For s = "", t = "ahbgdc":

• Init: i = 0 = len(s), return True.

Code with Explanation

Here’s the Python code using two pointers:

Copy codeclass Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # If s is empty, it's a subsequence
        if not s:
            return True

        # Two pointers
        i = 0  # For s
        for j in range(len(t)):
            if t[j] == s[i]:
                i += 1
                if i == len(s):
                    return True

        # Check if all of s was matched
        return i == len(s)

Explanation

• Lines 3-5: Handle empty s—O(1).
• Line 7: i: Pointer for s—O(1).
• Lines 8-12: Iterate t:
• If match, increment i—O(1).
• If i reaches len(s), return True—O(1).
• Line 14: Return True if all matched—O(1).
• Time: O(n)—single pass through t.
• Space: O(1)—two pointers.

This is like a string follower—quick and lean!

Alternative Solution: Dynamic Programming

Why an Alternative Approach?

The dynamic programming (DP) solution runs in O(m * n) time (m is length of s, n is length of t) with O(m * n) space by building a table to track subsequence lengths. It’s overkill—great for learning DP or handling more complex subsequence problems, but slower and space-heavy here!

How It Works

• DP Table: dp[i][j] = length of longest common subsequence of s[0:i] and t[0:j].
• Fill:
• If chars match, dp[i][j] = dp[i-1][j-1] + 1.
• Else, dp[i][j] = dp[i][j-1] (skip t char).
• Result: True if dp[m][n] = len(s).

Step-by-Step Example

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

• DP Table (1-based indexing for clarity, 0 row/col for empty):

a h b g d c 0 0 0 0 0 0 0 a 1 1 1 1 1 1 b 1 1 2 2 2 2 c 1 1 2 2 2 3

• Result: dp[3][6] = 3 = len(s), return True.

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

• DP Table:

a h b g d c 0 0 0 0 0 0 0 a 1 1 1 1 1 1 x 1 1 1 1 1 1 c 1 1 1 1 1 2

• Result: dp[3][6] = 2 < 3, return False.

Code with Explanation

Copy codeclass Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # Handle empty s
        if not s:
            return True

        # DP table: dp[i][j] = LCS length of s[0:i] and t[0:j]
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

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

        # Check if full s is matched
        return dp[m][n] == m

Explanation

• Lines 4-6: Handle empty s—O(1).
• Lines 8-9: dp: Table for LCS lengths—O(m * n).
• Lines 11-16: Fill table:
• Match: Add 1 to diagonal—O(1).
• No match: Take left (skip t char)—O(1).
• Line 18: True if LCS = len(s)—O(1).
• Time: O(m * n)—fill table.
• Space: O(m * n)—table size.

It’s a subsequence tracker—thorough but heavy!

Comparing the Two Solutions

• Two Pointers (Best):
• Time: O(n)—linear.
• Space: O(1)—minimal.
• Pros: Fast, space-efficient, simple.
• Cons: Less extensible.
• Dynamic Programming (Alternative):
• Time: O(m * n)—quadratic.
• Space: O(m * n)—table.
• Pros: Flexible for variants.
• Cons: Overkill, slow, space-heavy.

Two pointers win for efficiency and simplicity!

Additional Examples and Edge Cases

• s="a", t="a": Both return True.
• s="ab", t="ba": Both return False.
• Long t: Two pointers scale better.

Two pointers are optimal, DP works too.

Complexity Breakdown

• Two Pointers:
• Time: O(n).
• Space: O(1).
• DP:
• Time: O(m * n).
• Space: O(m * n).

Two pointers excel for performance.

Key Takeaways

• Two Pointers: Match in order—fast and lean!
• DP: Table it out—clear but heavy!
• Subsequence: Order matters.
• Python Tip: Loops rock—see [Python Basics](/python/basics).

Final Thoughts: Check That Subsequence

LeetCode 392: Is Subsequence in Python is a sequence challenge. Two pointers are the efficiency champ, while DP offers a robust alternative for learning. Want more? Try LeetCode 1143: Longest Common Subsequence or LeetCode 438: Find All Anagrams in a String. Ready to match? Visit Solve LeetCode 392 on LeetCode and verify that subsequence today!